Traveling Salesman Constants
Let 
be the smallest tour
length for 
points in a 
-D hypercube.
Then there exists a smallest constant 
such that
for all optimal tours in the hypercube,
 |
(1)
|
and a constant 
such that
for almost all optimal tours in the hypercube,
 |
(2)
|
These constants satisfy the inequalities
 |  |  |
(3)
|
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
 |  |  |
(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))),](/images/equations/TravelingSalesmanConstants/NumberedEquation3.gif) |
(10)
|
is the gamma
function, 
is an expression
involving Struve functions and Bessel
functions of the second kind,
 |
(11)
|
(OEIS A086306; Karloff 1989), and
 |
(12)
|
(OEIS A086307; Goddyn 1990).
In the limit 
,
 |  |  |
(13)
|
 |  |  |
(14)
|
 |  |  |
(15)
|
and
 |
(16)
|
where
![1/2<=theta=lim_(d->infty)[theta(d)]^(1/d)<=0.6602,](/images/equations/TravelingSalesmanConstants/NumberedEquation7.gif) |
(17)
|
and 
is the best sphere
packing density in 
-D space (Goddyn
1990, Moran 1984, Kabatyanskii and Levenshtein 1978). Steele and Snyder (1989) proved
that the limit 
exists.
Now consider the constant
 |
(18)
|
so
 |
(19)
|
Nonrigorous numerical estimates give 
(Johnson et al. 1996) and 
(Percus and Martin 1996).
A certain self-avoiding space-filling function is an optimal tour through a set of 
points, where 
can be arbitrarily large. It has length
 |
(20)
|
(OEIS A073008), where 
is the length
of the curve at the 
th iteration and
is the point-set size (Norman and
Moscato 1995).
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 
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." https://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.
Weisstein, Eric W. "Traveling Salesman Constants." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TravelingSalesmanConstants.html
Contact the MathWorld Team
traveling salesman
problem