greenline
rgstripes
Otto-Bild Stephan Mertens - Publications
Home | Research | Publications | Teaching | Smorgasbord
greenline

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)

greenline
rgstripes
top Home | Research | Publications | Teaching | Smorgasbord
greenline

© by Stephan Mertens
URL: http://
updated on Sunday, April 17th 2005, 10:27:33 CET;