Zero-temperature scaling and combinatorial optimization
- 27 April 1987
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 58 (17) , 1703-1706
- https://doi.org/10.1103/physrevlett.58.1703
Abstract
Combinatorial optimization problems such as the determination of the ground-state energy of Ising spin-glasses, the construction of low-autocorrelation binary sequences, and the traveling salesman problem are analyzed with use of zero-temperature scaling concepts. The difficulty of obtaining good ground states with most heuristic algorithms is influenced by the number of local minima. It is shown that the number of such minima is related to the thermal eigenvalue at the zero-temperature fixed point.Keywords
This publication has 21 references indexed in Scilit:
- Application of statistical mechanics to NP-complete problems in combinatorial optimisationJournal of Physics A: General Physics, 1986
- Lower Critical Dimension of Metallic Vector Spin-GlassesPhysical Review Letters, 1986
- A replica analysis of the travelling salesman problemJournal de Physique, 1986
- Configuration space analysis of travelling salesman problemsJournal de Physique, 1985
- Computer-intractability of the frustration model of a spin glassJournal of Physics A: General Physics, 1984
- Scaling theory of Ising spin glassesJournal of Physics C: Solid State Physics, 1984
- Optimization by Simulated AnnealingScience, 1983
- Residual magnetic entropy and metastable states of the Edwards-Anderson Ising spin glassJournal of Physics A: General Physics, 1983
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982
- Metastable states in spin glasses with short-ranged interactionsJournal of Physics C: Solid State Physics, 1981