# 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](https://doi.org/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](https://doi.org/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](https://doi.org/10.1016/j.orl.2019.11.007)
4. Z. Dong and J. Cao, "New bounds for the Euclidean TSP constant" (2026). [arXiv:2610.02809](https://arxiv.org/abs/2610.02809)

## Source

Imported from [Optimization Constants in Mathematics, constant 12](https://teorth.github.io/optimizationproblems/constants/12a.html), 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.