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

(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

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

 

---

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

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength