8.1 Introduction

Almost all of the results surveyed here owe a debt of one sort or another to the classic theorem of Beardwood, Halton, and Hammersley that lays out the basic behavior of the length of the shortest tour through a random sample from a general distribution in Rd:

Theorem 8.1 (Beardwood et al., 1959) If Xi, are independently and identically distributed random variables with bounded support in Rd, then the length Ln under the usual Euclidean metric of the shortest path through the points {X1, X2, ... , Xn} satisfies

Here, f(x) is the density of the absolutely continuous part of the distribution of the Xi, and βTSP, d is a positive constant that depends on d but not on the distribution of the Xi.

The Beardwood, Halton, and Hammersley (BHH) theorem has led to developments of several different types. The first developments that we review concern generalizations of the BHH theorem that aim to provide insight into larger classes of processes. It turns out that the essential geometric features of the TSP are present in many of the problems that have been investigated in the theory of combinatorial optimization, and there is also a close connection between these properties and the notions of subadditivity. These subadditivity-driven generalizations of the BHH are addressed primarily in §8.2.

The second type of problem considered looks at the BHH theorem from the perspective of precision, rather than generality. It turns out that Ln, the length of the shortest tour through an n-sample, is highly concentrated about its mean. The main result of this development, the theorem of Rhee and Talagrand, is spelled out in §8.3. It tells us that the tails of the TSP functional Ln decay as rapidly as those of the normal distribution. This remarkable result has evolved through several intermediate stages, each of which offered new tools for the analysis of functionals of finite point sets in the plane.

Section 8.4 is the last to focus explicitly on the theory of the TSP, and, though we start to strain the notion of a Euclidean problem, the development casts light on problems like those just described. The main purpose of §8.4 is

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement