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

The Easiest Hard Problem: Number Partitioning

Stephan Mertens


Abstract

Number partitioning is one of the classical NP-hard problems of combinatorial optimization. It has applications in areas like public key encryption and task scheduling. The random version of number partitioning has an “easy-hard” phase transition similar to the phase transitions observed in other combinatorial problems like K-SAT. In contrast to most other problems, number partitioning is simple enough to obtain detailled and rigorous results on the “hard” and “easy” phase and the transition that separates them. We review the known results on random integer partitioning, give a very simple derivation of the phase transition and discuss the algorithmic implications of both phases.


BiBTeX Entry

@InProceedings{,
  author = 	 {Stephan Mertens},
  title = 	 {The Easiest Hard Problem: Number Partitioning},
  booktitle = 	 {Computational Complexity and Statistical Physics},
  year =	 {2006},
  pages =        {125--139},
  editor =	 {A.G. Percus and G. Istrate and C. Moore},
  address =	 {New York},
  publisher =	 {Oxford University Press},
  note =	 {\url{http://arxiv.org/abs/cond-mat/0302536}}
}

Download:
npp5.pdf (pdf, 520 k)

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

© by Stephan Mertens
URL: http://
updated on Saturday, February 11th 2006, 00:32:09 CET;