# Berlin 2008 – wissenschaftliches Programm

## 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^{1}, Wolfgang Radenbach^{2}, and •Alexander Hartmann^{3} — ^{1}Institute for Theoretical Physics, University of Göttingen, Friedrich-Hund-Platz 1, 37077 Göttingen, Germany — ^{2}University of Göttingen, Platz der Göttinger Sieben 5, 37073 Göttingen, Germany — ^{3}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.