New Bounds for the Euclidean TSP Constant

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,\dots ,X_n$ in the unit square. It states that there exists a universal constant $\beta$ such that the length of the shortest tour is asymptotic to $\beta \sqrt{n}$ almost surely. The best bounds established to date are $0.6277\le \beta \le 0.90367$. In this paper, we improve these bounds to $0.6421\le \beta \le 0.8810$. Using importance sampling, we further show that $0.6536\le \beta \le 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.