The Beardwood–Halton–Hammersley constant
Description of constant
$C_{12} = \beta_{2}$ is the constant such that the length $L_{n}$ of the shortest tour through $n$ independent uniform random points satisfies $L_{n}/\sqrt{n}\to \beta_{2}$ almost surely.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $0.92117$ | [BHH1959] | Uses a strip-based constructive tour (horizontal slicing argument). Original reference contained some numerical errors [S2015] |
| $0.92117 - \frac{9}{16} 10^{-6}$ | [S2015] | Noted a slight improvement by allowing “zigzag” path corrections instead of a purely left-to-right tour. |
| $<0.90304$ | [YC2023] | Latest computer-aided proof that significantly lowers the upper bound. Uses numerical integration and search over tour patterns. |
| $0.8810$ | [DC2026] | Preprint. Blocks of six consecutive points in strips of height $2/\sqrt{n}$; one visiting order for each cell of a grid of $12^5\cdot 20^6$ cells, segment lengths bounded through second moments, rational arithmetic rounded in the safe direction. |
| $0.8618$* | [O2026] | The construction of [DC2026] with blocks of ten consecutive points in strips of height $2.2/\sqrt{n}$; the expected length of each segment is bounded by the Edmundson–Madansky inequality on a mesh finer than the grid. Gap cells bounded by $3/8$, $7/8$, $13/8$, six height cells, mesh $1/128$ in each gap and $64$ intervals in each height cell, last gap cell truncated $16$ units beyond its left end. An integer computation gives $\beta \le 5A/(6^{10}\cdot 2^{32}\cdot 9\cdot 11)$ with $A = 4430997795015293889$, that is $0.861715646305$; three programs (Python, C, Rust) agree, and the total is also evaluated in Lean 4 with native_decide. Programs and data at commit f5d1842 of the repository. Asterisked: computer-assisted, and the source is a self-archived preprint. |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $0.625$ | [BHH1959] | Obtained by subadditivity and geometric arguments ensuring a minimum tour length contribution per point. |
| $0.625 + \frac{19}{10368} \approx 0.6268$ | [S2015] | A refined analysis using nearest-neighbor distances; contained errors fixed in [GJ2020]. |
| $0.6277$ | [GJ2020] | Improved rigorous lower bound using an approach based on nearest-neighbor distances, correcting and tightening a prior argument of [S2015]. |
Additional comments and links
- Extensive experiments (using the Held–Karp relaxation and exact solvers) suggest that $\beta_2$ is about 0.71 to three significant figures. [JMR1996], [C2012]
References
- [BHH1959] Beardwood, J.; Halton, J. H.; Hammersley, J. M. (1959). The shortest path through many points. Proc. Cambridge Philosophical Society 55(4): 299–327. DOI: 10.1017/S0305004100034095.
- [C2012] Cook, W. (2012). In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press. ISBN: 9780691152707.
- [DC2026] Dong, Z.; Cao, J. (2026). New bounds for the Euclidean TSP constant. Preprint. arXiv:2610.02809.
- [GJ2020] Gaudio, J.; Jaillet, P. (2020). An improved lower bound for the Traveling Salesman constant. Operations Research Letters 48(1): 67–70. arXiv:1907.02390. DOI: 10.1016/j.orl.2019.11.007.
- [JMR1996] Johnson, D. S.; McGeoch, L. A.; Rothberg, E. E. (1996). Asymptotic experimental analysis for the Held–Karp traveling salesman bound. In Proc. 7th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 341–350.
- [O2026] O’Keefe, D. (2026). An upper bound for the Euclidean travelling salesman constant. Preprint. Paper, programs and data: https://github.com/devinokeefe/travelling-sales-person-constant-bounds.
- [S2015] Steinerberger, S. (2015). New bounds for the traveling salesman constant. Advances in Applied Probability 47(1): 27–36. arXiv:1311.6338 (preprint). DOI: 10.1239/aap/1427814579.
- [YC2023] Yu, J.; Carlsson, J. G. (2023). A new upper bound for the Euclidean TSP constant. Preprint (Optimization Online, June 2023). (Forthcoming in INFORMS Journal on Computing.) Available at https://optimization-online.org/?p=23315.
Contribution notes
ChatGPT DeepResearch was used to prepare an initial version of this page.
The [O2026] row was added by its author; that work and this entry were prepared with AI assistance.