PreprintarXiv licencearXiv
New Bounds for the Euclidean TSP Constant
Abstract
The Beardwood-Halton-Hammersley theorem characterizes the asymptotic length of the optimal Euclidean traveling salesman tour through independent and uniformly distributed random points X1,…,Xn in the unit square. It states that there exists a universal constant β such that the length of the shortest tour is asymptotic to β√n almost surely. The best bounds established to date are 0.6277≤ β≤ 0.90367. In this paper, we improve these bounds to 0.6421≤β≤0.8810. Using importance sampling, we further show that 0.6536≤ β≤ 0.8749 holds with probability at least 1−2× 10−4. Here the probability is taken with respect to the randomness of the sampling procedure.
Related
- Euclidean SVP is deterministically NP-hard to approximate within any constant factor
- Bounds on the Semidefinite Programming Complexity of the Euclidean Ball
- Improved bounds for lines and $1$-separated sets in Euclidean Ramsey theory
- Sharp mean-width and Jacobian bounds for Euclidean and hyperbolic harmonic maps
- Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls
BibTeX
@misc{dong2026bounds,
title = {{New Bounds for the Euclidean TSP Constant}},
author = {Zhuolun Dong and Junyu Cao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02809},
eprint = {2610.02809},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02809},
}
RIS
TY - UNPB
TI - New Bounds for the Euclidean TSP Constant
AU - Zhuolun Dong
AU - Junyu Cao
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02809
UR - https://arxiv.org/abs/2610.02809
AB - 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,…,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 β√n almost surely. The best bounds established to date are 0.6277≤ β≤ 0.90367. In this paper, we improve these bounds to 0.6421≤β≤0.8810. Using importance sampling, we further show that 0.6536≤ β≤ 0.8749 holds with probability at least 1−2× 10^−4. Here the probability is taken with respect to the randomness of the sampling procedure.
ER -