Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
Phase transition and landscape statistics of the number partitioning problem
Peter F. Stadler, Wim Hordijk, José F. Fontanari
Download
Status: Published
Phys.Rev.E 67: 056701 (2003)
Abstract
The phase transition in the number partitioning problem (NPP), i.e., the transition from a region in the space of control parameters in which almost all instances have many solutions to a region in which almost all instances have no solution, is investigated by examining the energy landscape of this classic optimization problem. This is achieved by coding the information about the minimum energy paths connecting pairs of minima into a tree structure, termed a barrier tree, the leaves and internal nodes of which represent, respectively, the minima and the lowest energy saddles connecting those minima. Here we apply several measures of shape (balance and symmetry) as well as of branch lengths (barrier heights) to the barrier trees that result from the landscape of the NPP, aiming at identifying traces of the easy/hard transition. We find that it is not possible to tell the easy regime from the hard one by visual inspection of the trees or by measuring the barrier heights. Only the {\it difficulty} measure, given by the maximum value of the ratio between the barrier height and the energy surplus of local minima, succeeded in detecting traces of the phase transition in the tree. In adddition, we show that the barrier trees associated with the NPP are very similar to random trees, contrasting dramatically with trees associated with the $p$ spin-glass and random energy models. We also examine critically a recent conjecture on the equivalence between the NPP and a truncated random energy model.
Keywords
energy landscape, barrier trees, number partitioning problem, random energy models, tree balance
Note
Alternative Numbers: SFI 03-02-006, <a href="http://arxiv.org/abs/cond-mat/0302041">cond-mat/0302041</a>