On the statistical mechanics of optimization problems of the travelling salesman type

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 transition