Questions? Call 800-624-6242

| Items in cart [0]

PAPERBACK
price:\$52.75

## Probability and Algorithms (1992) Commission on Physical Sciences, Mathematics, and Applications (CPSMA)

### Citation Manager

. "8 Probability and Problems in Euclidean Combinatorial Optimization." Probability and Algorithms. Washington, DC: The National Academies Press, 1992.

 Page 110

The following HTML text is provided to enhance online readability. Many aspects of typography translate only awkwardly to HTML. Please use the page image as the authoritative form to ensure accuracy.

Probability and Algorithms

### 8.1Introduction

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

 Page 110
 Front Matter (R1-R10) 1 Introduction (1-16) 2 Simulated Annealing (17-30) 3 Approximate Counting Via Markov Chains (31-38) 4 Probabilistic Algorithms for Speedup (39-52) 5 Probabilistic Algorithms for Defeating Adversaries (53-64) 6 Pseudorandom Numbers (65-86) 7 Probabilistic Analysis of Packing and Related Partitioning Problems (87-108) 8 Probability and Problems in Euclidean Combinatorial Optimization (109-130) 9 Probabilistic Analysis in Linear Programming (131-148) 10 Randomization in Parallel Algorithms (149-160) 11 Randomly Wired Multistage Networks (161-174) 12 Missing Pieces, Derandomization, and Concluding Remarks (175-178)