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 kth neighbor.