Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T13:26:59.417Z Has data issue: false hasContentIssue false
  • English
  • Français

New Bounds for the Traveling Salesman Constant

Part of: Limit theorems Geometric probability and stochastic geometry

Published online by Cambridge University Press:  04 January 2016

Stefan Steinerberger
Stefan Steinerberger*
Affiliation:
Universität Bonn
*
∗ Current address: Department of Mathematics, Yale University, 10 Hillhouse Avenue, New Haven, CT 06520, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let X1, X2, …, Xn be independent and uniformly distributed random variables in the unit square [0, 1]2, and let L(X1, …, Xn) be the length of the shortest traveling salesman path through these points. In 1959, Beardwood, Halton and Hammersley proved the existence of a universal constant β such that limn→∞n−1/2L(X1, …, Xn) = β almost surely. The best bounds for β are still those originally established by Beardwood, Halton and Hammersley, namely 0.625 ≤ β ≤ 0.922. We slightly improve both upper and lower bounds.

Keywords

Traveling salesman constantBeardwood-Halton-Hammersley theorem

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry 60F17: Functional limit theorems; invariance principles
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 47 , Issue 1 , March 2015 , pp. 27 - 36
Copyright
© Applied Probability Trust 

References

Applegate, D. L., Bixby, R. E., Chvátal, V. and Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.Google Scholar
Avram, F. and Bertsimas, D. (1992). The minimum spanning tree constant in geometrical probability and under the independent model: a unified approach. Ann. Appl. Prob. 2, 113–130.Google Scholar
Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford University Press.CrossRefGoogle Scholar
Beardwood, J., Halton, J. H. and Hammersley, J. (1959). The shortest path through many points. Proc. Camb. Philos. Soc. 55, 299–327.CrossRefGoogle Scholar
Borovkov, A. A. (1962). A probabilistic formulation of two economic problems. Dokl. Akad. Nauk SSSR 146, 983–986 (in Russian).Google Scholar
Cook, W. J. (2012). In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press.Google Scholar
Fejes, L. (1940). Über einen geometrischen Satz. Math. Z. 46, 83–85.Google Scholar
Few, L. (1955). The shortest path and the shortest road through n points. Mathematika 2, 141–144.Google Scholar
Finch, S. R. (2003). Mathematical Constants (Encyclopedia Math. Appl. 94). Cambridge University Press.Google Scholar
Gutin, G. and Punnen, A. P. (eds) (2002). The Traveling Salesman Problem and Its Variations. Kluwer, Dordrecht.Google Scholar
Johnson, D. S., McGeoch, L. A. and Rothberg, E. E. (1996). Asymptotic experimental analysis for the Held–Karp traveling salesman bound. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 341–350.Google Scholar
Mathai, A. M. (1999). An Introduction to Geometrical Probability: Distributional Aspects with Applications (Statist. Distributions Models Appl. 1). Gordon and Breach, Amsterdam.Google Scholar
Percus, A. G. and Martin, O. C. (1996). Finite size and dimensional dependence in the Euclidean traveling salesman problem. Phys. Rev. Lett. 76, 1188–1191.Google Scholar
Redmond, C. and Yukich, J. E. (1994). Limit theorems and rates of convergence for Euclidean functionals. Ann. Appl. Prob. 4, 1057–1073.Google Scholar
Steele, J. M. (1981). Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Prob. 9, 365–376.Google Scholar
Steele, J. M. (1997). Probability Theory and Combinatorial Optimization (CBMS-NSF Regional Conf. Ser. Appl. Math. 69). SIAM, Philadelphia, PA.CrossRefGoogle Scholar
Valenzuela, C. L. and Jones, A. J. (1997). Estimating the Held–Karp lower bound for the geometric TSP. Europ. J. Operat. Res. 102, 157–175.Google Scholar
Venkatesh, S. S. (2012). The Theory of Probability: Explorations and Applications. Cambridge University Press.Google Scholar
Verblunsky, S. (1951). On the shortest path through a number of points. Proc. Amer. Math. Soc. 2, 904–913.CrossRefGoogle Scholar
Yukich, J. E. (1998). Probability Theory of Classical Euclidean Optimization Problems (Lecture Notes Math. 1675). Springer, Berlin.Google Scholar