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. |
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.
- [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.
- [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.