Random Costs in Combinatorial Optimization
arXiv:cond-mat/9907088 · doi:10.1103/PhysRevLett.84.1347
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.
4 pages, Revtex, 2 figures (eps), submitted to PRL
References in corpus (4)
Cited by in corpus (30)
- What is the Computational Value of Finite Range Tunneling?
- A collective phase in resource competition in a highly diverse ecosystem
- A physicist's approach to number partitioning
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
- Universality in the level statistics of disordered systems
- Number partitioning as random energy model
- Optimal combinations of imperfect objects
- Analysis of the Karmarkar-Karp Differencing Algorithm
- Number Partitioning with Grover's Algorithm in Central Spin Systems
- Clustering analysis of the ground-state structure of the vertex-cover problem
- Fast optimization algorithms and the cosmological constant
- Statistical Mechanics of an NP-complete Problem: Subset Sum
- Phase transition and landscape statistics of the number partitioning problem
- Microscopic realizations of the Trap Model
- Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random Satisfiability problem, and its application to stop-and-restart resolutions
- Simulations of the adiabatic quantum optimization for the Set Partition Problem
- Number Partitioning on a Quantum Computer
- Criticality of natural absorbing states
- Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
- Distribution of the number of fitness maxima in Fisher's Geometric Model
- Solution-space structure of (some) optimization problems
- Travelling Salesman Problem with a Center
- Entropy-based analysis of the number partitioning problem
- Dynamic phase diagram of the Number Partitioning Problem
- Analysis of landscape hierarchy during coarsening and aging in Ising spin glasses
- Computational Complexity for Physicists
- A simplified Parisi Ansatz II: REM universality
- A new REM conjecture
- Random-Energy Secret Sharing via Extreme Synergy
- A Grand-Canonical Solution to a Class of Random Optimization Problems