On the statistical mechanics of the traveling salesman problem

Baskaran, G. ; Fu, Yaotian ; Anderson, P. W. (1986) On the statistical mechanics of the traveling salesman problem Journal of Statistical Physics, 45 (1-2). pp. 1-25. ISSN 0022-4715

Full text not available from this repository.

Official URL: http://www.springerlink.com/content/v135h7318388m3...

Related URL: http://dx.doi.org/10.1007/BF01033073


We consider the statistical mechanics of the traveling salesman problem (TSP) and develop some representations to study it. In one representation the mean field theory has a simple form and brings out some of the essential features of the problem. It shows that the system has spontaneous symmetry breaking at any nonzero temperature. In general the phase progressively changes as one decreases the temperature. At low temperatures the mean field theory solution is very sensitive to any small perturbations, due to the divergence of some local susceptibilities. This critical region extends down to zero temperature. We perform the quenched average for a nonmetric TSP in the second representation and the resulting problem is more complicated than the infinite-range spin-glass problem, suggesting that the free energy landscape may be more complex. The role played by frustration in this problem appears explicitly through the localization property of a random matrix, which resembles the tight binding matrix of an electron in a random lattice.

Item Type:Article
Source:Copyright of this article belongs to Springer-Verlag.
Keywords:Spin Glass; N-P Complete Optimization Problems
ID Code:1869
Deposited On:08 Oct 2010 11:52
Last Modified:16 May 2011 10:01

Repository Staff Only: item control page