{"id":"arxiv/2610.02809","url":"https://arxiv.org/abs/2610.02809","tags":["math.PR","math.OC"],"score":0,"title":"New Bounds for the Euclidean TSP Constant","domain":"math.PR","source":"arxiv","authors":["Zhuolun Dong","Junyu Cao"],"reviews":0,"subject":"math.PR","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}