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

Phase Transition in the Number Partitioning Problem

Stephan Mertens

---

Abstract

Number partitioning is an NP-complete problem of combinatorial optimization. A statistical mechanics analysis reveals the existence of a phase transition that separates the easy from the hard to solve instances and that reflects the pseudo-polynomiality of number partitioning. The phase diagram and the value of the typical ground state energy are calculated.

---

BiBTeX Entry

@Article{,
  author  = {Stephan Mertens},
  title   = {Phase Transition in the Number Partitioning Problem},
  journal = {Phys.\ Rev.\ Lett.},
  year    = {1998},
  volume  = {81},
  number  = {20},
  pages   = {4281-4284},
  month   = {November}
}

---

Download:

npp1.ps.gz (gzip'ed postscript, 162 k) or npp1.pdf (PDF format, 119 k)