Probabilistic Analysis of the Number Partitioning Problem

Details Probabilistic Analysis of the Number Partitioning Problem Probabilistic Analysis of the Number Partitioning Problem

1998-01-14

arxiv.org/abs/adap-org/9801002v1

Physics

Condensed Matter

Statistical Mechanics

14 pages and 5 figures

Scientific paper

10.1088/0305-4470/31/15/007

Given a sequence of $N$ positive real numbers $\{a_1,a_2,..., a_N \}$, the number partitioning problem consists of partitioning them into two sets such that the absolute value of the difference of the sums of $a_j$ over the two sets is minimized. In the case that the $a_j$'s are statistically independent random variables uniformly distributed in the unit interval, this NP-complete problem is equivalent to the problem of finding the ground state of an infinite-range, random anti-ferromagnetic Ising model. We employ the annealed approximation to derive analytical lower bounds to the average value of the difference for the best constrained and unconstrained partitions in the large $N$ limit. Furthermore, we calculate analytically the fraction of metastable states, i.e. states that are stable against all single spin flips, and found that it vanishes like $N^{-3/2}$.

Affiliated with

Also associated with

No associations

Rating

Probabilistic 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 Probabilistic Analysis of the Number Partitioning Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic Analysis of the Number Partitioning Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-209949