| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Random Costs in Combinatorial Optimization | Stephan Mertens
; | Date: |
6 Jul 1999 | Subject: | Disordered Systems and Neural Networks; Statistical Mechanics | cond-mat.dis-nn cond-mat.stat-mech | Affiliation: | Otto-von-Guericke Universitat, Magdeburg | Abstract: | The random cost problem is the problem of finding the minimum in an exponentially long 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. This explains the bad performance of heuristic approaches to the number partitioning problem and allows us to calculate the probability distributions of the optimum and sub-optimum costs. | Source: | arXiv, cond-mat/9907088 | Other source: | [GID 707589] pmid11017515 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |