Regensburg 2007 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

DY: Fachverband Dynamik und Statistische Physik

DY 30: Poster II

DY 30.37: Poster

Donnerstag, 29. März 2007, 16:00–18:00, Poster D

Ground-state structure and energy landscape of the number partitioning problem — •Alexander Mann and Alexander K. Hartmann — Institut für Theoretische Physik, Georg-August-Universität Göttingen

We study the number partitioning problem (NPP), a basic NP-hard optimization problem which presents a phase transition between a computationally easy phase with an exponential number of zero energy solutions and a computationally hard phase with unique non-zero energy ground states. We apply both exact optimization algorithms and parallel tempering Monte Carlo simulations. To get an impression of the structure of the energy landscape we study the clustering properties in the easy as well as in the hard phase. We also study the finite-size scaling behavior of a temperature driven phase transition and compare it to analytical work and to the results of the random-energy model.