Berlin 2008 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe
DY: Fachverband Dynamik und Statistische Physik
DY 16: Glasses II (joint session DF/DY)
DY 16.1: Vortrag
Dienstag, 26. Februar 2008, 14:30–14:45, EB 407
Glassy Solution-Space Structure of Optimization Problems — Alexander Mann1, Wolfgang Radenbach2, and •Alexander Hartmann3 — 1Institute for Theoretical Physics, University of Göttingen, Friedrich-Hund-Platz 1, 37077 Göttingen, Germany — 2University of Göttingen, Platz der Göttinger Sieben 5, 37073 Göttingen, Germany — 3Institute for Physics, University of Oldenburg, 26111 Oldenburg, Germany
We study numerically the glassy solution-space cluster of random ensembles of two NP-hard optimization problems originating in computational complexity, the vertex-cover problem and the number partitioning problem. We use branch-and-bound type algorithms to obtain exact solutions of these problems for moderate system sizes. Using two methods, direct neighborhood-based clustering and hierarchical clustering, we investigate the structure of the solution space. The main result is that the correspondence between solution structure and the phase diagrams of the problems is not unique. Namely, for vertex cover we observe a drastic change of the solution space from large single clusters to multiple nested levels of clusters. In contrast, for the number-partitioning problem, the phase space looks always very simple, similar to a random distribution of the lowest-energy configurations. This holds in the “easy”/solvable phase as well as in the “hard”/unsolvable phase.