An Improved Lower Bound for the Traveling Salesman Constant

Julia Gaudio; Patrick Jaillet

arxiv: 1907.02390 · v1 · pith:NQBZKENUnew · submitted 2019-07-04 · 🧮 math.PR

An Improved Lower Bound for the Traveling Salesman Constant

Julia Gaudio , Patrick Jaillet This is my paper

Pith reviewed 2026-05-25 09:06 UTC · model grok-4.3

classification 🧮 math.PR

keywords traveling salesman problemBeardwood constantrandom points in the planelower boundsasymptotic analysisgeometric probabilityalmost sure convergence

0 comments

The pith

The Traveling Salesman constant β is at least 0.6277 almost surely.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper improves the known lower bound on the constant β that describes the length of the shortest tour through a large number of random points in the unit square. The limit of the tour length divided by the square root of the number of points converges almost surely to β, and the original 1959 proof gave β at least 0.625. By building on a 2015 method, the authors raise the lower bound to 0.6277. A reader would care because this constant controls the typical length of optimal solutions in many random geometric optimization problems, and tighter bounds constrain how efficient such tours can be.

Core claim

Let X1, X2, …, Xn be independent uniform random variables on [0,1]². Let L(X1,…,Xn) be the length of the shortest Traveling Salesman tour through these points. It is known that there exists a constant β such that lim n→∞ L(X1,…,Xn)/√n = β almost surely. The original analysis showed β ≥ 0.625. Building upon an approach proposed in Steinerberger 2015, the paper improves the lower bound to β ≥ 0.6277.

What carries the argument

Numerical extension of the Steinerberger 2015 method for producing lower bounds on the Beardwood-Halton-Hammersley constant β.

If this is right

The shortest tour length through n random points satisfies L ≥ 0.6277 √n for large n, almost surely.
The gap between the proven lower and upper bounds on β is narrowed from the 1959 value.
The same extension technique applies directly to the original Beardwood-Halton-Hammersley limit theorem without altering its almost-sure convergence statement.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The refined bound could be used to certify the quality of heuristic TSP solutions on large random instances more tightly than before.
Similar numerical refinements might improve lower bounds for related constants in the Euclidean matching problem or minimum spanning tree problem on random points.
If the method generalizes, it could be tested on points sampled from other distributions or in higher dimensions to produce dimension-dependent constants.

Load-bearing premise

The approach proposed in Steinerberger 2015 remains valid and can be extended without introducing new errors to produce the improved numerical bound of 0.6277.

What would settle it

A re-computation of the numerical integrals or optimization steps in the extended Steinerberger method that yields a value strictly less than 0.6277.

read the original abstract

Let $X_1, X_2, \dots, X_n$ be independent uniform random variables on $[0,1]^2$. Let $L(X_1, \dots, X_n)$ be the length of the shortest Traveling Salesman tour through these points. It is known that there exists a constant $\beta$ such that $$\lim_{n \to \infty} \frac{L(X_1, \dots, X_n)}{\sqrt{n}} = \beta$$ almost surely (Beardwood 1959). The original analysis in (Beardwood 1959) showed that $\beta \geq 0.625$. Building upon an approach proposed in (Steinerberger 2015), we improve the lower bound to $\beta \geq 0.6277$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

They raise the lower bound on the TSP constant from 0.625 to 0.6277 by numerically extending the Steinerberger 2015 construction.

read the letter

They raise the lower bound on the TSP constant from 0.625 to 0.6277 by extending the Steinerberger 2015 method. That's the main takeaway, and the only thing that would matter to someone following this line of work. The paper takes the construction from the 2015 paper, which involves a lower bound derived from expectations over point processes, and then improves the numerical estimate of that lower bound. They report the new value 0.6277 as the result of that extension. No new framework is proposed, and the abstract makes clear that the gain comes from carrying the prior method further. This counts as honest progress because it delivers a concrete, better number without overclaiming. In areas where exact values are unknown, these kinds of refinements are how the field moves forward, and the authors have done the calculation needed to move the needle from the Beardwood original to this point. The potential weakness lies in the numerical step. Improving the bound requires minimizing or integrating a more complex functional than before, and the accuracy of 0.6277 rests on that computation being correct and global. If the discretization is too coarse or the optimization misses a better point, the reported improvement could be overstated. The paper would be stronger with some discussion of how they validated the numerical result, but the abstract does not mention it. The argument does not suffer from circularity or invented quantities. It is a straightforward extension. This is work for a small group of people interested in asymptotic constants for random geometric problems. A reader not already following the TSP constant literature would not find much to engage with. I think it should go to peer review. The claim is narrow but well-defined, and a referee can evaluate whether the numerical improvement holds up. It is not important enough for broad attention, but it is the sort of paper that belongs in a specialized journal after review.

Referee Report

1 major / 0 minor

Summary. The manuscript extends the construction from Steinerberger (2015) to obtain a numerical lower bound β ≥ 0.6277 for the Beardwood-Halton-Hammersley constant governing the asymptotic length of the shortest TSP tour through n uniform random points in the unit square, improving on the 1959 analytic bound of 0.625.

Significance. If the numerical improvement is rigorously supported, the result supplies a modestly tighter explicit lower bound on a central constant in geometric probability. The approach is constructive and builds directly on prior work without introducing new free parameters or ad-hoc entities.

major comments (1)

[Abstract (and any computational section describing the extension)] The headline numerical claim β ≥ 0.6277 rests entirely on the output of a discretized minimization or integration step that extends the 2015 functional. No error bounds, grid-resolution analysis, or verification that the reported minimum is global appear in the manuscript; any local-minimum or quadrature bias would directly falsify the claimed improvement over 0.625.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for highlighting the need for rigorous justification of the numerical improvement. We agree that the current manuscript lacks explicit error analysis for the discretized computation and will revise accordingly to strengthen the claim.

read point-by-point responses

Referee: [Abstract (and any computational section describing the extension)] The headline numerical claim β ≥ 0.6277 rests entirely on the output of a discretized minimization or integration step that extends the 2015 functional. No error bounds, grid-resolution analysis, or verification that the reported minimum is global appear in the manuscript; any local-minimum or quadrature bias would directly falsify the claimed improvement over 0.625.

Authors: We acknowledge this gap: the manuscript presents the numerical value 0.6277 without accompanying error bounds, grid-convergence analysis, or arguments for globality of the minimum. In the revision we will add a dedicated computational section that (i) specifies the discretization parameters, (ii) derives explicit a-priori error bounds for the quadrature and minimization steps that are sufficient to guarantee the strict improvement over 0.625, and (iii) supplies numerical evidence (multiple random initializations, comparison with finer grids) supporting that the reported value is not an artifact of a local minimum. These additions will make the numerical claim fully rigorous. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bound obtained by extending independent external method

full rationale

The paper's central claim improves the Beardwood 1959 analytic lower bound of 0.625 by extending the approach from the independent Steinerberger 2015 paper to reach the numerical value 0.6277. No derivation step within this manuscript reduces by construction to a self-defined quantity, a fitted parameter renamed as a prediction, or a self-citation chain. The result is presented as a direct numerical extension of an external construction and remains falsifiable against that prior work and the original Beardwood analysis.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities beyond reliance on the existence result from Beardwood 1959 and the method from Steinerberger 2015.

axioms (1)

domain assumption Existence of the limit β (Beardwood 1959)
The paper takes the almost-sure convergence result as given.

pith-pipeline@v0.9.0 · 5657 in / 996 out tokens · 40566 ms · 2026-05-25T09:06:50.698379+00:00 · methodology

An Improved Lower Bound for the Traveling Salesman Constant

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)