The statistical mechanics of traveling salesman type problems

David S. Dean (1, 2) , David Lancaster (3) , Satya Majumdar (4, 1, 5)

1 PhyStat - Physique Statistique des Systèmes Complexes (LPT)
2 DAMTP - Department of Applied Mathematics and Theoretical Physics
3 Harrow School of Computer Science - University of Westminster
4 LPTMS - Laboratoire de Physique Théorique et Modèles Statistiques
5 LPT - Laboratoire de Physique Théorique

We study the finite temperature statistical mechanics of Hamiltonian paths between a set of N quenched randomly distributed points in a finite domain D. The energy of the path is a function of the distance between neighboring points on the path, an example is the traveling salesman problem where the energy is the total distance between neighboring points on the path. We show how the system can be analyzed in the limit of large N without using the replica method.

Domaines: Systèmes désordonnés et réseaux de neurones [cond-mat.dis-nn]

David S. Dean, David Lancaster, Satya Majumdar. The statistical mechanics of traveling salesman type problems. Journal of Statistical Mechanics: Theory and Experiment, 2005, 1, pp.L01001. ⟨10.1088/1742-5468/2005/01/L01001⟩. ⟨hal-00004567⟩