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

Random Costs in Combinatorial Optimization

Stephan Mertens

---

Abstract

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

@Article{,
  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:
npp2.ps.gz (gzip'ed postscript, 87 k) or npp2.pdf (PDF format, 83 k)