The Beardwood–Halton–Hammersley theorem (1959) states that the length LnL_n of the optimal traveling salesman tour through nn independent uniformly distributed random points in the unit square satisfies Ln/n→βL_n/\sqrt{n} \to \beta almost surely for a universal constant β\beta, the traveling salesman constant. The exact value of β\beta is unknown: the rigorous bounds of Gaudio–Jaillet (2020) and Gaudio–Guan (2026) are 0.6277≤β≤0.903670.6277 \le \beta \le 0.90367, while large-scale computation suggests β≈0.71\beta \approx 0.71. The question posed in Gaudio and Jaillet's lower-bound paper is whether the rigorous lower bound on β\beta can be improved beyond 0.62770.6277, and, more broadly, whether the wide gap between the certified bounds can be substantially closed, ultimately toward determining β\beta exactly.

Background

The traveling salesman problem (TSP) asks for the shortest closed tour visiting a given set of points. In the random Euclidean version, X1,X2,…,XnX_1, X_2, \dots, X_n are independent points distributed uniformly in the unit square [0,1]2[0,1]^2, and L(X1,…,Xn)L(X_1, \dots, X_n) denotes the length of the optimal (shortest) tour under the ordinary Euclidean distance. A classical theorem of Beardwood, Halton, and Hammersley (1959) states that the ratio L(X1,…,Xn)/nL(X_1, \dots, X_n)/\sqrt{n} converges almost surely — that is, with probability 1 over the random point set — to a universal constant β\beta, called the traveling salesman constant. This constant is fundamental: it is the asymptotic proportionality factor between optimal tour length and n\sqrt{n} for uniformly distributed demand, it underlies the probabilistic analysis of partitioning and routing heuristics, and it enters continuous-approximation models in logistics, where the cost of serving many randomly located customers in a region of area AA scales like βA⋅m\beta\sqrt{A \cdot m} for mm customers. Analogous constants govern other subadditive Euclidean functionals — random optimization quantities over point sets that behave approximately additively under subdivision of the region, such as minimum spanning tree and minimum matching lengths. Despite its centrality, the numerical value of β\beta is unknown. Beardwood, Halton, and Hammersley proved 0.625≤β≤β+0.625 \le \beta \le \beta_+, where the upper bound β+\beta_+ is the explicit integral β+=2∫0∞∫03z12+z22 e−3z1(1−z2/3) dz2 dz1≈0.92116\beta_+ = 2\int_0^\infty \int_0^{\sqrt{3}} \sqrt{z_1^2 + z_2^2}\, e^{-\sqrt{3} z_1} (1 - z_2/\sqrt{3})\, dz_2\, dz_1 \approx 0.92116, obtained by an explicit strip (band) construction of a tour; a large-scale computational study (Applegate, Bixby, Chvátal, and Cook, 2006) estimates β≈0.71\beta \approx 0.71. The lower bound of 0.625=12(12+34)0.625 = \frac{1}{2}(\frac{1}{2} + \frac{3}{4}) comes from a nearest-neighbor counting argument: in any valid tour each point is connected to exactly two other points, so summing, per point, half the distances to its two nearest neighbors gives a valid lower bound; these distances are evaluated by replacing the uniform points with a Poisson point process of intensity nn (a model of random points in which the numbers of points in disjoint regions are independent, and which removes finite-nn discretization effects). The expected distances from a typical point to its nearest and second-nearest neighbors are 12n\frac{1}{2\sqrt{n}} and 34n\frac{3}{4\sqrt{n}}, giving β≥0.625\beta \ge 0.625. Steinerberger (2015) proposed improving both bounds. His upper-bound improvement — a tiny reduction by an explicit ϵ0>916⋅10−6\epsilon_0 > \frac{9}{16} \cdot 10^{-6} — stands, but his claimed lower-bound improvement contained a bookkeeping error in how edge lengths are counted when correcting the nearest-neighbor construction; Gaudio and Jaillet (2020) identified the fault, corrected the argument, and pushed it further. The idea is that connecting every point to its two nearest neighbors creates short cycles — in particular triangles — which no valid tour may contain. One identifies point configurations that force a triangle (for instance, a point whose third-nearest neighbor lies at distance r3≥r1+2r2r_3 \ge r_1 + 2r_2, where r1,r2r_1, r_2 are its two nearest-neighbor distances), and then corrects the accounting: subtract the triangle's edge-length contribution and add a rigorous lower bound on the replacement connections. Gaudio and Jaillet's corrected computation gives β≥58+1910368≈0.6268\beta \ge \frac{5}{8} + \frac{19}{10368} \approx 0.6268, and tightening the triangle inequality by conditioning on which half-plane the triangle's third point falls in — which improves the worst-case triangle side from r1+r2r_1 + r_2 to r12+r22\sqrt{r_1^2 + r_2^2} with probability 12\frac{1}{2} — yields β≥58+12⋅1910368+12⋅30722−43255376≥0.6277\beta \ge \frac{5}{8} + \frac{1}{2} \cdot \frac{19}{10368} + \frac{1}{2} \cdot \frac{3072\sqrt{2} - 4325}{5376} \ge 0.6277. They note explicitly that there is room to improve the lower bound further. On the upper-bound side, which had seen essentially no progress since 1959, Carlsson and Yu (2026; preprint 2023) introduced a computer-aided proof — certified numerical quadrature combined with a decision-tree search over band-traversal tour constructions — showing β<0.9038\beta < 0.9038, and Gaudio and Guan (2026) refined the band construction with crossovers to β≤0.90367\beta \le 0.90367, while showing that the existing computer-aided framework is limited to roughly 0.880.88 without new ideas. The rigorous bounds certified by these arguments are 0.6277≤β≤0.903670.6277 \le \beta \le 0.90367, against an empirically estimated value of ≈0.71\approx 0.71.

Problem Statement

Determine the Beardwood–Halton–Hammersley constant β\beta — the almost-sure limit of L(X1,…,Xn)/nL(X_1, \dots, X_n)/\sqrt{n} as n→∞n \to \infty, where X1,X2,…,XnX_1, X_2, \dots, X_n are independent uniformly distributed random points in the unit square and LL is the length of the optimal Euclidean traveling salesman tour through them. The exact value of β\beta is unknown and no closed-form or rigorously computable representation of it is known. The concrete task posed by Gaudio and Jaillet (2020) is to prove a rigorous lower bound strictly exceeding the exact value of the bound they certify, 58+12⋅1910368+12⋅30722−43255376≈0.6277266\frac{5}{8} + \frac{1}{2} \cdot \frac{19}{10368} + \frac{1}{2} \cdot \frac{3072\sqrt{2} - 4325}{5376} \approx 0.6277266 (their published statement of that bound is the rounded β≥0.6277\beta \ge 0.6277). Substantially shrinking the certified gap between the rigorous lower bound 0.62770.6277 and the rigorous upper bound 0.903670.90367, toward the computationally estimated value ≈0.71\approx 0.71 and ultimately toward the exact determination of β\beta, is a broader goal.

References

  1. Beardwood, J., Halton, J. H., Hammersley, J. M. (1959). The shortest path through many points. Mathematical Proceedings of the Cambridge Philosophical Society 55(4):299–327. doi:10.1017/S0305004100034095. https://doi.org/10.1017/S0305004100034095
  2. Steinerberger, S. (2015). New Bounds for the Traveling Salesman Constant. Advances in Applied Probability 47(1):27–36. doi:10.1239/aap/1427814579. https://doi.org/10.1239/aap/1427814579 (preprint arXiv:1311.6338, https://arxiv.org/abs/1311.6338)
  3. Gaudio, J., Jaillet, P. (2020). An improved lower bound for the Traveling Salesman constant. Operations Research Letters 48(1):67–70. doi:10.1016/j.orl.2019.11.007. https://doi.org/10.1016/j.orl.2019.11.007 (preprint arXiv:1907.02390, https://arxiv.org/abs/1907.02390)
  4. Carlsson, J. G., Yu, J. (2026). A New Upper Bound for the Euclidean TSP Constant. INFORMS Journal on Computing 38(2):341–356. doi:10.1287/ijoc.2024.0538. https://doi.org/10.1287/ijoc.2024.0538 (preprint 2023)
  5. Gaudio, J., Guan, C. K. (2026). An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers. arXiv:2602.11250, doi:10.48550/arXiv.2602.11250, https://arxiv.org/abs/2602.11250 (published as Operations Research Letters 69 (2026) 107492, doi:10.1016/j.orl.2026.107492, https://doi.org/10.1016/j.orl.2026.107492)
  6. Applegate, D. L., Bixby, R. E., Chvátal, V., Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics. Princeton University Press. ISBN 978-0-691-12993-8; ebook (2011) doi:10.1515/9781400841103, https://doi.org/10.1515/9781400841103