OpenFrontiers
Join
← Back to the index
OP-12013OpenProbability

The Beardwood–Halton–Hammersley constant (C12C_{12})

The Beardwood–Halton–Hammersley constant: determine C12C_{12} or improve its bounds; the repository records 0.6277 (lower) and 0.90304 (upper).

MSC 60D05 · Geometric probability and stochastic geometryMSC 90C27 · Combinatorial optimization

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

C12=β2C_{12} = \beta_{2} is the constant such that the length LnL_{n} of the shortest tour through nn independent uniform random points satisfies Ln/n→β2L_{n}/\sqrt{n}\to \beta_{2} almost surely.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • Extensive experiments (using the Held–Karp relaxation and exact solvers) suggest that β2\beta_2 is about 0.71 to three significant figures. [JMR1996], [C2012]

References (from the repository page)

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

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 0.6277; best known upper bound 0.90304. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
0.921170.92117 [BHH1959] Uses a strip-based constructive tour (horizontal slicing argument). Original reference contained some numerical errors [S2015]
0.92117−91610−60.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<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.6250.625 [BHH1959] Obtained by subadditivity and geometric arguments ensuring a minimum tour length contribution per point.
0.625+1910368≈0.62680.625 + \frac{19}{10368} \approx 0.6268 [S2015] A refined analysis using nearest-neighbor distances; contained errors fixed in [GJ2020].
0.62770.6277 [GJ2020] Improved rigorous lower bound using an approach based on nearest-neighbor distances, correcting and tightening a prior argument of [S2015].
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — The Beardwood–Halton–Hammersley constant ($C_{12}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.