New Bounds for the Traveling Salesman Constant
Stefan Steinerberger · Advances in Applied Probability · 2015
Let X 1 , X 2 , …, X n be independent and uniformly distributed random variables in the unit square [0, 1] 2 , and let L ( X 1 , …, X n ) be the length of the shortest traveling salesman path through these points. In 1959, Beardwood, Halton and Hammersley proved the existence of a universal constant β such that lim n →∞ n −1/2 L ( X 1 , …, X n ) = β almost surely. The best bounds for β are still those originally established by Beardwood, Halton and Hammersley, namely 0.625 ≤ β ≤ 0.922. We slightly improve both upper and lower bounds.