New Bounds for the Euclidean TSP Constant

Source abstract

The Beardwood-Halton-Hammersley theorem characterizes the asymptotic length of the optimal Euclidean traveling salesman tour through independent and uniformly distributed random points $X_1,\ldots,X_n$ in the unit square. It states that there exists a universal constant $β$ such that the length of the shortest tour is asymptotic to $β\sqrt{n}$ almost surely. The best bounds established to date are $0.6277\leq β\leq 0.90367$. In this paper, we improve these bounds to $0.6421\leqβ\leq0.8810$. Using importance sampling, we further show that $0.6536\leq β\leq 0.8749$ holds with probability at least $1-2\times 10^{-4}$. Here the probability is taken with respect to the randomness of the sampling procedure.