Entropy-based analysis of the number partitioning problem

Details Entropy-based analysis of the number partitioning problem Entropy-based analysis of the number partitioning problem

2000-07-26

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

Phys. Rev. E, vol. 63, 020106(R) (2001)

Physics

Condensed Matter

Disordered Systems and Neural Networks

6 pages, 4 figures

Scientific paper

10.1103/PhysRevE.63.020106

In this paper we apply the multicanonical method of statistical physics on the number-partitioning problem (NPP). This problem is a basic NP-hard problem from computer science, and can be formulated as a spin-glass problem. We compute the spectral degeneracy, which gives us information about the number of solutions for a given cost $E$ and cardinality $m$. We also study an extension of this problem for $Q$ partitions. We show that a fundamental difference on the spectral degeneracy of the generalized ($Q>2$) NPP exists, which could explain why it is so difficult to find good solutions for this case. The information obtained with the multicanonical method can be very useful on the construction of new algorithms.

Affiliated with

Also associated with

No associations

Rating

Entropy-based analysis 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 Entropy-based analysis of the number partitioning problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Entropy-based analysis of the number partitioning problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-719616