Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

DF: Fachverband Dielektrische Festkörper

DF 8: Glasses II (joint session DF/DY)

DF 8.1: Vortrag

Dienstag, 26. Februar 2008, 14:30–14:45, EB 407

Glassy Solution-Space Structure of Optimization Problems — Alexander Mann¹, Wolfgang Radenbach², and •Alexander Hartmann³ — ¹Institute for Theoretical Physics, University of Göttingen, Friedrich-Hund-Platz 1, 37077 Göttingen, Germany — ²University of Göttingen, Platz der Göttinger Sieben 5, 37073 Göttingen, Germany — ³Institute 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.