Mean-field theory for optimization problems
- 1 January 1985
- journal article
- Published by EDP Sciences in Journal de Physique Lettres
- Vol. 46 (17), 763-770
- https://doi.org/10.1051/jphyslet:019850046017076300
Abstract
A mean-field theory for optimization problems of the Travelling Salesman type, or of the Matching type, is presented. It involves an infinite set of order parameters which measure the lack of self-averageness of the system and its degree of freezing. We further conjecture that NP-completeness is associated with replica symmetry breakingKeywords
This publication has 11 references indexed in Scilit:
- Spin-Glass Model of Crystal SurfacesPhysical Review Letters, 1985
- Nature of the Spin-Glass PhasePhysical Review Letters, 1984
- On the statistical mechanics of optimization problems of the travelling salesman typeJournal de Physique Lettres, 1984
- Order Parameter for Spin-GlassesPhysical Review Letters, 1983
- Optimization by Simulated AnnealingScience, 1983
- Metastable states in spin glassesJournal of Physics C: Solid State Physics, 1980
- Stability of the Sherrington-Kirkpatrick solution of a spin glass modelJournal of Physics A: General Physics, 1978
- Solutions of Flexible Polymers. Neutron Experiments and InterpretationMacromolecules, 1975
- Theory of spin glassesJournal of Physics F: Metal Physics, 1975
- The shortest path through many pointsMathematical Proceedings of the Cambridge Philosophical Society, 1959