




Random Costs in Combinatorial Optimization
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 NPhard 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 suboptimum costs.
BiBTeX Entry
@Article{, author = {Stephan Mertens}, title = {Random Costs in Combinatorial Optimization}, journal = {Phys.\ Rev.\ Lett.}, year = {2000}, volume = {84}, number = {6}, pages = {13471350}, month = {February} }
Download:
npp2.ps.gz (gzip'ed postscript, 87 k) or
npp2.pdf (PDF format, 83 k)





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