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." Mathematika2, 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.
B50, 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. B37, 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 Fractals6, 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.
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,
such that for almost all optimal tours in the
hypercube,
![gamma_d=(Gamma(3+1/d)[Gamma(1/2d+1)]^(1/d))/(2sqrt(pi)(d^(1/2)+d^(-1/2))),](/images/equations/TravelingSalesmanConstants/NumberedEquation3.svg)
is the gamma function, 
is an expression involving Struve
functions and Bessel functions
of the second kind,
,
![1/2<=theta=lim_(d->infty)[theta(d)]^(1/d)<=0.6602,](/images/equations/TravelingSalesmanConstants/NumberedEquation7.svg)
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.
(Johnson et al. 1996) and 
(Percus and Martin 1996).
points, where 
can be arbitrarily large. It has length
is the length of the curve at the 
th iteration and 
is the point-set size (Norman and Moscato 1995).
Points." Mathematika 2, 141-144, 1955.Finch, S. R.
"Traveling Salesman Constants." §8.5 in