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),

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


These constants satisfy the inequalities


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


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


(OEIS A086306; Karloff 1989), and


(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)
<=lim sup_(d->infty)beta(d)<=lim_(d->infty)12^(1/(2d))6^(-1/2)





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




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


(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


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.", 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.

Subject classifications