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

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)

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

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