TOPICS
Search

Traveling Salesman Constants

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The traveling salesman constants describe the asymptotic lengths of shortest closed tours through point sets in the traveling salesman problem. For an integer d>=2, let L(n,d) be the length of the shortest tour, measured using Euclidean distance, through a specified set of n points in the unit hypercube [0,1]^d. The worst-case constant alpha(d) is the smallest constant such that, for every sequence of these point sets,

limsup_(n->infty)(L(n,d))/(n^((d-1)/d)sqrt(d))<=alpha(d).
(1)

If the points are the first n members of a sequence of independent and identically distributed points drawn from the uniform distribution on [0,1]^d, then a constant beta(d) satisfies, almost surely,

lim_(n->infty)(L(n,d))/(n^((d-1)/d)sqrt(d))=beta(d).
(2)

These constants satisfy the inequalities

0.44194<gamma_2=5/(16)sqrt(2)<=beta(2)
(3)
<=delta<0.6508<0.75983<3^(-1/4)<=alpha(2)
(4)
<=phi<0.98398
(5)
0.37313<gamma_3<=beta(3)<=12^(1/6)6^(-1/2)<0.61772<0.64805
(6)
<2^(1/6)3^(-1/2)<=alpha(3)<=psi<0.90422
(7)
0.34207<gamma_4<=beta(4)<=12^(1/8)6^(-1/2)<0.55696
(8)
<0.59460<2^(-3/4)<=alpha(4)<=0.8364
(9)

(Fejes Tóth 1940, Verblunsky 1951, Few 1955, Beardwood et al. 1959), where

gamma_d=(Gamma(3+1/d)[Gamma(1/2d+1)]^(1/d))/(2sqrt(pi)(d^(1/2)+d^(-1/2))),
(10)

Gamma(z) is the gamma function, delta is an expression involving Struve functions and Bessel functions of the second kind,

phi=(280(3-sqrt(3)))/(840-280sqrt(3)+4sqrt(5)-sqrt(10))
(11)

(OEIS A086306; Karloff 1989), and

psi=1/23^(-2/3)(4+3ln3)^(2/3)
(12)

(OEIS A086307; Goddyn 1990).

In the limit d->infty,

0.24197<lim_(d->infty)gamma_d=1/(sqrt(2pie))<=liminf_(d->infty)beta(d)
(13)
<=limsup_(d->infty)beta(d)<=lim_(d->infty)12^(1/(2d))6^(-1/2)
(14)
=1/(sqrt(6))<0.40825
(15)

and

0.24197<1/(sqrt(2pie))<=liminf_(d->infty)alpha(d)<=limsup_(d->infty)alpha(d)<=(2(3-sqrt(3))theta)/(sqrt(2pie))<0.4052,
(16)

where

1/2<=theta=limsup_(d->infty)[theta(d)]^(1/d)<=0.6602,
(17)

and theta(d) is the best sphere packing density in d-D space (Kabatyanskii and Levenshtein 1978, Moran 1984, Goddyn 1990, Cohn and Zhao 2014). For each fixed d>=2, Steele and Snyder (1989) proved that the maximum of L(n,d) over n-point sets in [0,1]^d, divided by n^((d-1)/d)sqrt(d), converges to alpha(d) as n->infty.

For the random points described above with d=2, consider the constant

kappa=lim_(n->infty)(L(n,2))/(sqrt(n))=beta(2)sqrt(2),
(18)

so

5/8=gamma_2sqrt(2)<=kappa<=deltasqrt(2)<0.9204.
(19)

Nonrigorous numerical estimates give kappa approx 0.7124 (Johnson et al. 1996) and kappa approx 0.7120 (Percus and Martin 1996).

For independent and identically distributed points drawn from the uniform distribution on the unit square, Dong and Cao (2026) improved the rigorous bounds to

0.6421<=kappa<=0.8810.
(20)

Their constant beta is kappa=sqrt(2)beta(2) in the notation used here. Dong and Cao (2026) also obtained the interval 0.6536<=kappa<=0.8749 with confidence at least 1-2×10^(-4) from importance sampling. This confidence refers to the randomness of the sampling procedure, not to randomness of kappa.

A certain self-avoiding space-filling function is an optimal tour through a set of n points, where n can be arbitrarily large. It has length

lambda=lim_(m->infty)(L_m)/(sqrt(n_m))=(4(1+2sqrt(2))sqrt(51))/(153)=0.7147827...
(21)

(OEIS A073008), where L_m is the length of the curve at the mth iteration and n_m is the point-set size (Norman and Moscato 1995).

See also

Traveling Salesman Problem

Explore with Wolfram|Alpha

References

Applegate, D. L.; Bixby, R. E.; Chvátal, V.; Cook, W.; Espinoza, D. G.; Goycoolea, M.; and Helsgaun, K. "Certification of an Optimal TSP Tour Through 85,900 Cities." Oper. Res. Lett. 37, 11-15, 2009.Beardwood, J.; Halton, J. H.; and Hammersley, J. M. "The Shortest Path through Many Points." Proc. Cambridge Phil. Soc. 55, 299-327, 1959.Chartrand, G. "The Salesman's Problem: An Introduction to Hamiltonian Graphs." §3.2 in Introductory Graph Theory. New York: Dover, pp. 67-76, 1985.Cohn, H. and Zhao, Y. "Sphere Packing Bounds via Spherical Codes." Duke Math. J. 163, 1965-2002, 2014. https://doi.org/10.1215/00127094-2738857.Dong, Z. and Cao, J. "New Bounds for the Euclidean TSP Constant." 2 Oct 2026. https://arxiv.org/abs/2610.02809.Fejes Tóth, L. "Über einen geometrischen Satz." Math. Zeit. 46, 83-85, 1940.Few, L. "The Shortest Path and the Shortest Road through n Points." Mathematika 2, 141-144, 1955.Finch, S. R. "Traveling Salesman Constants." §8.5 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 497-503, 2003.Flood, M. "The Travelling Salesman Problem." Operations Res. 4, 61-75, 1956.Goddyn, L. A. "Quantizers and the Worst Case Euclidean Traveling Salesman Problem." J. Combin. Th. Ser. B 50, 65-81, 1990.Johnson, D. S.; McGeoch, L. A.; and Rothberg, E. E. "Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound." In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM and Philadelphia, PA: SIAM, pp. 341-350, 1996.Kabatyanskii, G. A. and Levenshtein, V. I. "Bounds for Packing on a Sphere and in Space." Problems Inform. Transm. 14, 1-17, 1978.Karloff, H. J. "How Long Can a Euclidean Traveling Salesman Tour Be?" SIAM J. Disc. Math. 2, 91-99, 1989.Moran, S. "On the Length of Optimal TSP Circuits in Sets of Bounded Diameter." J. Combin. Th. Ser. B 37, 113-141, 1984.Moscato, P. "Fractal Instances of the Traveling Salesman Constant." http://www.ing.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.html.Norman, M. G. and Moscato, P. "The Euclidean Traveling Salesman Problem and a Space-Filling Curve." Chaos Solitons Fractals 6, 389-397, 1995.Percus, A. G. and Martin, O. C. "Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem." Phys. Rev. Lett. 76, 1188-1191, 1996.Sloane, N. J. A. Sequences A073008, A086306, and A086307 in "The On-Line Encyclopedia of Integer Sequences."Steele, J. M. and Snyder, T. L. "Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization." SIAM J. Comput. 18, 278-287, 1989.Verblunsky, S. "On the Shortest Path through a Number of Points." Proc. Amer. Math. Soc. 2, 904-913, 1951.

Referenced on Wolfram|Alpha

Traveling Salesman Constants

Cite this as:

Weisstein, Eric W. "Traveling Salesman Constants." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TravelingSalesmanConstants.html

Subject classifications