Given *n* points (“cities”) with random distances between them, what are the properties of the shortest closed path (“tour”) passing through all the cities?

Our numerical estimates from 1996 for the 2- and 3-dimensional traveling salesman constant are still the most precise ones to date, along with simultaneous results by David Johnson, et al. David Aldous and I have also studied how the length of a tour scales under small perturbations from optimality. This property appears to classify discrete optimization problems into a small number of distinct categories, reminiscent of universality classes in physics. Finally, for the non-metric problem where lengths between cities are i.i.d. random variables, ongoing work using the cavity method is leading to a precise conjecture on the probability with which an optimal tour connects a city to its *k*th neighbor.

- C. Wang, J.D. Hyman, A.G. Percus and R. Caflisch, “Parallel tempering for the traveling salesman problem,”
*International Journal of Modern Physics C***20**, 539-556 (2009). - A.G. Percus, “The traveling salesman problem and kth-nearest neighbors,” Los Alamos report LA-UR 06-6896 (2006).
- D. Aldous and A.G. Percus, “Scaling and universality in continuous length combinatorial optimization,”
*Proceedings of the National Academy of Sciences***100**, 11211-11215 (2003). - A.G. Percus and O.C. Martin, “The stochastic traveling salesman problem: Finite size scaling and the cavity prediction,”
*Journal of Statistical Physics***94**, 739-758 (1999). - A.G. Percus and O.C. Martin, “Scaling universalities of
*k*th-nearest neighbor distances on closed manifolds,”*Advances in Applied Mathematics***21**, 424-436 (1998). - N.J. Cerf, J. Boutet de Monvel, O. Bohigas, O.C. Martin and A.G. Percus, “The random link approximation for the Euclidean traveling salesman problem,”
*Journal de Physique I***7**, 117-136 (1997). - A.G. Percus and O.C. Martin, “Finite size and dimensional dependence of the Euclidean traveling salesman problem,”
*Physical Review Letters***76**, 1188-1191 (1996). - A.G. Percus,
*The Traveling Salesman and Related Stochastic Problems*. Ph.D. thesis, UniversitÃ© Pierre et Marie Curie, Paris (1997).