The travelling salesman constant (Beardwood–Halton–Hammersley)

The shortest tour through $n$ random points in a unit square has length close to $\beta\sqrt{n}$ for a universal constant $\beta$. Simulations put $\beta$ near 0.71, but rigorous bounds are far apart, and recent progress comes from computer-assisted proofs whose arithmetic can be rerun.

Problem

Let $X_1, X_2, \dots$ be independent points distributed uniformly in the unit square $[0,1]^2$, and let $L_n$ be the length of the shortest closed tour visiting $X_1, \dots, X_n$. Beardwood, Halton and Hammersley proved that there is a constant $\beta$ such that

$$\frac{L_n}{\sqrt{n}} \to \beta \quad \text{almost surely as } n \to \infty.$$

Determine $\beta$, or narrow the rigorous bounds $0.6277 \le \beta \le 0.8810$.

Background

The theorem (1959) says that the random Euclidean travelling salesman problem has a deterministic leading-order answer, so the whole difficulty is concentrated in one number. Upper bounds come from analysing explicit tour-building strategies, for example sweeping the square in strips and visiting points in a clever order; lower bounds come from local arguments, such as the distances from each point to its nearest neighbours. Both sides have been sharpened by computer-assisted proofs.

What is known

• Upper bounds: $0.92117$ (Beardwood, Halton and Hammersley, 1959, with small numerical errors noted later); $0.92117 - \tfrac{9}{16}10^{-6}$ (Steinerberger, 2015); about $0.903$ (Yu and Carlsson, 2023, computer-aided); $0.8810$ (Dong and Cao, October 2026 preprint), from blocks of six consecutive points in thin strips, with rational arithmetic rounded in the safe direction.
• Lower bounds: $0.625$ (Beardwood, Halton and Hammersley, 1959); about $0.6268$ (Steinerberger, 2015, with errors fixed later); $0.6277$ (Gaudio and Jaillet, 2020). The same Dong–Cao preprint also proves the lower bound $0.6421$, which the source does not list yet.
• Unverified claim: $\beta \le 0.8618$ (O'Keefe, 2026, self-archived), extending the Dong–Cao construction to blocks of ten points, with programs in three languages and a Lean evaluation of the final sum; the source marks it as awaiting independent verification.
• Experiments: large-scale computations suggest $\beta \approx 0.71$ (Johnson, McGeoch and Rothberg, 1996), far from both rigorous bounds.

What would count as progress

• A rigorous upper bound below $0.8810$ (or an independent check of the claimed $0.8618$): a tour strategy plus a computer-assisted bound on its expected length per point, with code that reproduces the exact rational or interval arithmetic.
• A rigorous lower bound above $0.6421$, or an independent check of the Dong–Cao bounds.
• A strategy-free improvement, such as a new local inequality, that a referee can verify by hand.

References

1. J. Beardwood, J. H. Halton and J. M. Hammersley, "The shortest path through many points", Mathematical Proceedings of the Cambridge Philosophical Society 55 (1959), 299–327. doi:10.1017/S0305004100034095
2. S. Steinerberger, "New bounds for the traveling salesman constant", Advances in Applied Probability 47 (2015), 27–36. doi:10.1239/aap/1427814579
3. J. Gaudio and P. Jaillet, "An improved lower bound for the traveling salesman constant", Operations Research Letters 48 (2020), 67–70. doi:10.1016/j.orl.2019.11.007
4. Z. Dong and J. Cao, "New bounds for the Euclidean TSP constant" (2026). arXiv:2610.02809

Source

Imported from Optimization Constants in Mathematics, constant 12, curated by Terence Tao and contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.