Math Conjectures

Beardwood–Halton–Hammersley planar TSP constant

OPENMajorExact constant problemProposed 1959 · Standard version

Canonical statement

Let X1,X2,…X_1,X_2,\ldots be independent random points uniformly distributed on [0,1]2[0,1]^2, and let LnL_n be the minimum Euclidean length of a closed polygonal tour visiting X1,…,XnX_1,\ldots,X_n. The almost-sure limit
β2=lim⁡n→∞Lnn \beta_2=\lim_{n\to\infty}\frac{L_n}{\sqrt n}
exists and is a deterministic positive constant. Determine β2\beta_2 exactly.
View source LaTeX
Let \(X_1,X_2,\ldots\) be independent random points uniformly distributed on \([0,1]^2\), and let \(L_n\) be the minimum Euclidean length of a closed polygonal tour visiting \(X_1,\ldots,X_n\). The almost-sure limit
\[
\beta_2=\lim_{n\to\infty}\frac{L_n}{\sqrt n}
\]
exists and is a deterministic positive constant. Determine \(\beta_2\) exactly.
OR-003:[BeardwoodHaltonHammersley1959][GaudioJaillet2020][CarlssonYu2023][GaudioGuan2026BandCrossovers]
Operations researchProbability theory

Notes

Beardwood, Halton, and Hammersley proved in 1959 that if LnL_n is the length of a shortest closed tour through nn independent uniform random points in the unit square, then Ln/nL_n/\sqrt n converges almost surely to a deterministic constant β2\beta_2 [BeardwoodHaltonHammersley1959]. Their subadditivity argument establishes existence but yields no closed form; the problem is to determine β2\beta_2 exactly.

Numerically the constant is well located, with Monte Carlo experiments placing it near 0.71240.7124. Rigorous knowledge is much cruder. The best published lower bound is 0.62770.6277, due to Gaudio and Jaillet [GaudioJaillet2020]. On the upper side, Carlsson and Yu developed a new upper-bound technique [CarlssonYu2023], and a 2026 preprint of Gaudio and Guan, using band crossovers, brings the rigorous upper bound down to 0.903670.90367 [GaudioGuan2026BandCrossovers], still well above the empirical value.

The problem remains open: no exact expression for β2\beta_2 is known, and even narrowing the rigorous bounds toward the simulated value, let alone identifying the constant exactly, appears to require substantially new ideas.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.