Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T22:23:46.225Z Has data issue: false hasContentIssue false

New Bounds for the Traveling Salesman Constant

Published online by Cambridge University Press:  04 January 2016

Stefan Steinerberger*
Affiliation:
Universität Bonn
*
∗ Current address: Department of Mathematics, Yale University, 10 Hillhouse Avenue, New Haven, CT 06520, USA. Email address: stefan.steinerberger@yale.edu
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 X 1, X 2, …, X n be independent and uniformly distributed random variables in the unit square [0, 1]2, and let L(X 1, …, X n ) 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/2 L(X 1, …, X n ) = β 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.

Information

Type
Stochastic Geometry and Statistical Applications
Copyright
© Applied Probability Trust