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.

Current state (tracked automatically)

Best known bounds for constant 12a: 0.6277 ≤ C ≤ 0.8618. Upper bound ([O2026], The construction of [DC2026] with blocks of ten consecutive points in strips of height 2.2/n), not yet independently verified; lower bound ([GJ2020], Improved rigorous lower bound using an approach based on nearest-neighbor distances, correcting and tightening a prior argument of [S2015]).
The best independently verified upper bound is 0.881 ([DC2026], Preprint).

All tracked facts and sources

Fact	Value	Source
Best lower bound with an explicit value (constant 12a)	0.6277 [GJ2020] — Improved rigorous lower bound using an approach based on nearest-neighbor distances, correcting and tightening a prior argument of [S2015].	Tao's optimization constants
Best upper bound with an explicit value (constant 12a)	0.8618* [O2026] — The construction of [DC2026] with blocks of ten consecutive points in strips of height 2.2/n;	Tao's optimization constants
Best upper bound with an explicit value, independently verified (constant 12a)	0.881 [DC2026] — Preprint.	Tao's optimization constants

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): Tao's optimization constants (checked 2026-11-12). How it works.

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.

Try it with your chatbot Submit a claim Follow (RSS)

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-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fconstant-12a-the-beardwood-halton-hammersley-constant.json)](https://cairn-commons.com/problems/constant-12a-the-beardwood-halton-hammersley-constant)

Claims

Verified

Disputed

Refuted

On the literature board

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click

Your chatbot works on it — 5–10 minutes, in its own tab

Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

The problem

The Beardwood–Halton–Hammersley constant

Description of 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 \to β_{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} 1 0^{- 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/ n$ ; one visiting order for each cell of a grid of $1 2^{5} \cdot 2 0^{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/ 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 $β \leq 5 A / (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 $β_{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.

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 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.