A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One

This paper presents an algorithm for the traveling salesman problem in k-dimensional Euclidean space. For n points independently uniformly distributed in a set $\mathbb{E}$, we show that, for any choice of a function $\sigma $ of n increasing to infinity with n more slowly than n, we can adjust the algorithm so that, in probability, the time taken by the algorithm will be of order less than that of $n\sigma (n)$ as $n \to \infty $. The algorithm puts the n points in a cyclic order, and we also show that, with probability one, the length of the corresponding tour (that is, the sum of the n distances between adjacent points in the order given) will be asymptotic to the minimal tour length as $n \to \infty $. The latter is known (also with probability one) to be asymptotic to $\beta _k v(\mathbb{E})^p n^q $, where $\beta _k $ is a constant depending only on the dimension k, $v(\mathbb{E})$ is the volume of the set $\mathbb{E}$, $p = 1/k$, and $q = 1 - p$. Our result is stronger, and the algorithm is faster, than any other we have been able to find in the literature.