Probabilistic Analysis of the Number Partitioning Problem
Ferreira, F F ; Fontanari, J F
arXiv, 9801002 / Harvested from arXiv
Text on arXiv
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}$.
Publié le : 1998-01-14
Classification:  Nonlinear Sciences - Adaptation and Self-Organizing Systems,  Condensed Matter - Statistical Mechanics,  Mathematical Physics 
@article{9801002,
     author = {Ferreira, F F and Fontanari, J F},
     title = {Probabilistic Analysis of the Number Partitioning Problem},
     journal = {arXiv},
     volume = {1998},
     number = {0},
     year = {1998},
     language = {en},
     url = {http://dml.mathdoc.fr/item/9801002}
}

Ferreira, F F; Fontanari, J F. Probabilistic Analysis of the Number Partitioning Problem. arXiv, Tome 1998 (1998) no. 0, . http://gdmltest.u-ga.fr/item/9801002/