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

Random Costs in Combinatorial Optimization

Stephan Mertens


The random cost problem is the problem of identifying the minimum in a list of random numbers. By definition, this problem cannot be solved faster than by exhaustive search. It is shown that a classical NP-hard optimization problem, number partitioning, is essentially equivalent to the random cost problem. On the one hand this explains the bad performance of heuristic approaches to the number partitioning problem, but on the other hand it allows one to calculate the probability distributions of the optimum and sub-optimum costs.

BiBTeX Entry

  author  = {Stephan Mertens},
  title   = {Random Costs in Combinatorial Optimization},
  journal = {Phys.\ Rev.\ Lett.},
  year    = {2000},
  volume  = {84},
  number  = {6},
  pages   = {1347-1350},
  month   = {February}

Download: (gzip'ed postscript, 87 k) or npp2.pdf (PDF format, 83 k)

top Home | Research | Publications | Teaching | Smorgasbord

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