Phase transition and landscape statistics of the number partitioning problem

Details Phase transition and landscape statistics of the number partitioning problem Phase transition and landscape statistics of the number partitioning problem

2003-02-07

arxiv.org/abs/cond-mat/0302155v1

Physics

Condensed Matter

Scientific paper

10.1103/PhysRevE.67.056701

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.

Affiliated with

Also associated with

No associations

Rating

Phase transition and landscape statistics of the number partitioning problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Phase transition and landscape statistics of the number partitioning problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase transition and landscape statistics of the number partitioning problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-294730