Document Detail


Random costs in combinatorial optimization
MedLine Citation:
PMID:  11017515     Owner:  NLM     Status:  Publisher    
Abstract/OtherAbstract:
The random cost problem is the problem of indentifying 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 suboptimum costs.
Authors:
Mertens
Related Documents :
5947615 - The problem of routine circumcision.
19426045 - The problem of temporal scale in optimization: three contrasting views of hummingbird v...
21161575 - Phenotypic overlap between core diagnostic features and emotional/behavioral problems i...
11017515 - Random costs in combinatorial optimization
7325265 - Bereavement counseling for gay individuals.
20227015 - Sectionable cassette for embedding automation in surgical pathology.
Publication Detail:
Type:  JOURNAL ARTICLE    
Journal Detail:
Title:  Physical review letters     Volume:  84     ISSN:  1079-7114     ISO Abbreviation:  Phys. Rev. Lett.     Publication Date:  2000 Feb 
Date Detail:
Created Date:  2000-10-05     Completed Date:  -     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  0401141     Medline TA:  Phys Rev Lett     Country:  UNITED STATES    
Other Details:
Languages:  Eng     Pagination:  1347-50     Citation Subset:  -    
Affiliation:
Institut fur Theoretische Physik, Universitat Magdeburg, Universitatsplatz 2, D-39106 Magdeburg, Germany.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  A space-time adaptive method for simulating complex cardiac dynamics.
Next Document:  From massively parallel algorithms and fluctuating time horizons to nonequilibrium surface growth