On the statistical mechanics of optimization problems of the travelling salesman type
Authors:
- 1 January 1984
- journal article
- Published by EDP Sciences in Journal de Physique Lettres
- Vol. 45 (24) , 1145-1153
Abstract
We show that two very different temperature regimes exist for problems of the travelling salesman type, and that the annealed approximation is valid for the high-temperature regime. Random-link models are introduced, for which upper and lower bounds on the free energy are obtained in the low-temperature regime. A soluble model is presented, which possesses a phase transition strongly reminiscent of the spin-glass transitionKeywords
This publication has 4 references indexed in Scilit:
- On the connection between spin glasses and gauge field theoriesPhysics Reports, 1980
- Random-Energy Model: Limit of a Family of Disordered ModelsPhysical Review Letters, 1980
- Computer Solutions of the Traveling Salesman ProblemBell System Technical Journal, 1965
- The shortest path through many pointsMathematical Proceedings of the Cambridge Philosophical Society, 1959