TOPICS
Search

Traveling Salesman Constants


Let L(n,d) be the smallest tour length for n points in a d-D hypercube. Then there exists a smallest constant alpha(d) such that for all optimal tours in the hypercube,

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

and a constant beta(d) such that for almost all optimal tours in the hypercube,

 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))<=lim inf_(d->infty)beta(d)
(13)
<=lim sup_(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))<=lim_(d->infty)alpha(d)<=(2(3-sqrt(3))theta)/(sqrt(2pie))<0.4052,
(16)

where

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

and theta(d) is the best sphere packing density in d-D space (Goddyn 1990, Moran 1984, Kabatyanskii and Levenshtein 1978). Steele and Snyder (1989) proved that the limit alpha(d) exists.

Now 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).

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...
(20)

(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.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 Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Held in San Francisco, California, January 22-24, 1995. Philadelphia, PA: ACM, 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 Web Resource. https://mathworld.wolfram.com/TravelingSalesmanConstants.html

Subject classifications