A replica analysis of the travelling salesman problem
- 1 January 1986
- journal article
- Published by EDP Sciences in Journal de Physique
- Vol. 47 (8), 1285-1296
- https://doi.org/10.1051/jphys:019860047080128500
Abstract
We propose and analyse a replica symmetric solution for random link travelling salesman problems. This gives reasonable analytical estimates for thermodynamic quantities such as the length of the shortest pathKeywords
This publication has 9 references indexed in Scilit:
- Configuration space analysis of travelling salesman problemsJournal de Physique, 1985
- Mean-field theory for optimization problemsJournal de Physique Lettres, 1985
- The microstructure of ultrametricityJournal de Physique, 1985
- The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis AlgorithmSIAM Review, 1984
- 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
- An application of physical methods to the computer aided design of electronic circuitsJournal de Physique Lettres, 1984
- Order Parameter for Spin-GlassesPhysical Review Letters, 1983
- Coexistence of Spin-Glass and Ferromagnetic OrderingsPhysical Review Letters, 1981