Traveling Salesman Constants

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

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,

$$\limsup_{n\to\infty} {L(n,d)\over n^{(d-1)/d}\sqrt{d}}\leq\alpha(d),$$ (1)

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

$$\lim_{n\to\infty} {L(n,d)\over n^{(d-1)/d}\sqrt{d}}=\beta(d).$$ (2)

These constants satisfy the inequalities

$0.44194<\gamma_2={\textstyle{5\over 16}}\sqrt{2} \leq\beta(2)$
$\leq\delta<0.6508<0.75983<3^{-1/4}\leq\alpha(2)\leq \phi< 0.98398\quad$	(3)

$0.37313<\gamma_3\leq\beta(3)\leq 12^{1/6}6^{-1/2}<0.61772<0.64805$
$<2^{1/6}3^{-1/2}\leq\alpha(3)\leq 0.90422\quad$	(4)

$0.34207<\gamma_4\leq\beta(4)\leq 12^{1/8}6^{-1/2}<0.55696$
$<0.59460<2^{-3/4}\leq\alpha(4)\leq 0.8364\quad$	(5)

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

$$\gamma_d\equiv{\Gamma\left({3+{1\over d}}\right)[\Gamma({\te... ...yle{1\over 2}}d+1)]^{1/d}\over 2\sqrt{\pi}(d^{1/2}+d^{-1/2})},$$ (6)

$\Gamma(z)$ is the Gamma Function, $\delta$ is an expression involving Struve Functions and Neumann Functions,

$$\phi\equiv {280(3-\sqrt{3}\,)\over 840-280\sqrt{3}+4\sqrt{5}-\sqrt{10}}$$ (7)

(Karloff 1989), and

$$\psi\equiv {\textstyle{1\over 2}}3^{-2/3}(4+\ln 3)^{2/3}$$ (8)

(Goddyn 1990). In the Limit $d\to\infty$,

$0.24197<\lim_{d\to\infty} \gamma_d = {1\over\sqrt{2\pi e}}\leq \liminf_{d\to\infty}\beta(d)$
$\leq \limsup_{d\to\infty}\beta(d) \leq \lim_{d\to\infty} 12^{1/(2d)}6^{-1/2}={1\over\sqrt{6}}<0.40825\quad$	(9)

and

$$0.24197<{1\over\sqrt{2\pi e}}\leq \lim_{d\to\infty} \alpha(d)\leq {2(3-\sqrt{3}\,)\theta\over \sqrt{2\pi e}}<0.4052,$$ (10)

where

$${\textstyle{1\over 2}}\leq \theta = \lim_{d\to\infty} [\theta(d)]^{1/d}\leq 0.6602,$$ (11)

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\equiv\lim_{n\to\infty} {L(n,2)\over\sqrt{n}}=\beta(2)\sqrt{2},$$ (12)

so

$${\textstyle{5\over 8}}=\gamma_2\sqrt{2}\leq\kappa\leq\delta\sqrt{2}<0.9204.$$ (13)

The best current estimate is $\kappa\approx 0.7124$.

A certain self-avoiding Space-Filling Curve is an optimal Tour through a set of $n$ points, where $n$ can be arbitrarily large. It has length

$$\lambda\equiv \lim_{m\to\infty} {L_m\over\sqrt{n_m}}={4(1+2\sqrt{2}\,)\sqrt{51}\over 153}=0.7147827\ldots,$$ (14)

where $L_m$ is the length of the curve at the $m$th iteration and $n_m$ is the point-set size (Moscato and Norman).

References

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. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/sales/sales.html

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.

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

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.