Stephan Mertens - Publications Home | Research | Publications | Teaching | Smorgasbord

A physicist's approach to number partioning

Stephan Mertens

---

Abstract

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 is essentially equivalent to locating the minimum in an unsorted list of O(2^N) numbers. Considering this equivalence it is not surprising that known heuristics for the partitioning problem are not significantly better than simple random search.

---

BiBTeX Entry

@article{,
  author =	 {Stephan Mertens},
  title =	 {A physicist's approach to number partitioning},
  journal =	 {Theoretical Computer Science},
  volume =       {265},
  number =       {1-2},
  pages =        {79--108},
  year =	 {2001}
}

---

Download:
npp3.ps.gz (gzip'ed postscript, 175 k)