Physics – Condensed Matter
Scientific paper
2000-09-15
Physics
Condensed Matter
35 pages, to appear in J. Theor. Comp. Science, typo corrected in eq.14
Scientific paper
The statistical physics approach to the number partioning problem, a classical NP-hard problem, is both simple and rewarding. Very basic notions and methods from statistical mechanics are enough to obtain analytical results for the phase boundary that separates the ``easy-to-solve'' from the ``hard-to-solve'' phase of the NPP as well as for the probability distributions of the optimal and sub-optimal solutions. In addition, it can be shown that solving a number partioning problem of size $N$ to some extent corresponds to locating the minimum in an unsorted list of $\bigo{2^N}$ numbers. Considering this correspondence it is not surprising that known heuristics for the partitioning problem are not significantly better than simple random search.
No associations
LandOfFree
A physicist's approach to number partitioning 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 A physicist's approach to number partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A physicist's approach to number partitioning will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-371626