The traveling salesman problem, conformal invariance, and dense polymers

Jesper-Lykke Jacobsen 1, Nicholas Read 2, Hubert Saleur 3, 4

Physical Review Letters 93 (2004) 038701

We propose that the statistics of the optimal tour in the planar random Euclidean traveling salesman problem is conformally invariant on large scales. This is exhibited in power-law behavior of the probabilities for the tour to zigzag repeatedly between two regions, and in subleading corrections to the length of the tour. The universality class should be the same as for dense polymers and minimal spanning trees. The conjectures for the length of the tour on a cylinder are tested numerically.

  • 1. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
    CNRS : UMR8626 – Université Paris XI - Paris Sud
  • 2. Department of Physics,
    Yale University
  • 3. Department of Physics and Astronomy,
    University of Southern California
  • 4. Service de Physique Théorique (SPhT),
    CNRS : URA2306 – CEA : DSM/SPHT