New Bounds for the Traveling Salesman Constant

Abstract

Let $X_1,X_2,\dots ,X_n$ be independent and uniformly distributed random variables in the unit square $[0,1{]}^2$ and let $L(X_1,\dots ,X_n)$ be the length of the shortest traveling salesman path through these points. In 1959, Beardwood, Halton $\&$ Hammersley proved the existence of a universal constant $\beta$ such that $$ \lim_{n \rightarrow \infty}{n^{-1/2}L(X_1, \dots, X_n)} = β\qquad \mbox{almost surely.}$$ The best bounds for $\beta$ are still the ones originally established by Beardwood, Halton $\&$ Hammersley $0.625\le \beta \le 0.922$. We slightly improve both upper and lower bounds.