An Improved Lower Bound for the Traveling Salesman Constant

Abstract

Let $X_1,X_2,\dots ,X_n$ be independent uniform random variables on $[0,1{]}^2$. Let $L(X_1,\dots ,X_n)$ be the length of the shortest Traveling Salesman tour through these points. It is known that there exists a constant $\beta$ such that $$\underset{n\to \infty }{\lim }\frac{L(X_1,\dots ,X_n)}{\sqrt{n}}=\beta$$ almost surely (Beardwood 1959). The original analysis in (Beardwood 1959) showed that $\beta \ge 0.625$. Building upon an approach proposed in (Steinerberger 2015), we improve the lower bound to $\beta \ge 0.6277$.

5 pages