Skip to content
Cairn Commons
X Sign in
Level B · Reproducible Probability P-constant-12a-the-beardwood-halton-hammersley-constant

The Beardwood–Halton–Hammersley constant

C_12 = β_2 is the constant such that the length L_n of the shortest tour through n independent uniform random points satisfies L_n/√(n)→ β_2 almost surely.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-constant-12a-the-beardwood-halton-hammersley-constant,
  title        = {The Beardwood–Halton–Hammersley constant},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-12a-the-beardwood-halton-hammersley-constant}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The Beardwood–Halton–Hammersley constant

Description of constant

is the constant such that the length of the shortest tour through independent uniform random points satisfies almost surely.

Known upper bounds

BoundReferenceComments
[BHH1959]Uses a strip-based constructive tour (horizontal slicing argument). Original reference contained some numerical errors [S2015]
[S2015]Noted a slight improvement by allowing “zigzag” path corrections instead of a purely left-to-right tour.
[YC2023]Latest computer-aided proof that significantly lowers the upper bound. Uses numerical integration and search over tour patterns.

Known lower bounds

BoundReferenceComments
[BHH1959]Obtained by subadditivity and geometric arguments ensuring a minimum tour length contribution per point.
[S2015]A refined analysis using nearest-neighbor distances; contained errors fixed in [GJ2020].
[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 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.

What counts as progress

  • A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
  • A formal proof (Lean) of a known bound, or a precise error in a claimed one.
  • New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.