Probability theory and combinatorial optimization

J. Michael Steele9780898713800, 0898713803

This monograph provides an introduction to the state of the art of the probability theory that is most directly applicable to combinatorial optimization. The questions that receive the most attention are those that deal with discrete optimization problems for points in Euclidean space, such as the minimum spanning tree, the traveling-salesman tour, and minimal-length matchings. Still, there are several nongeometric optimization problems that receive full treatment, and these include the problems of the longest common subsequence and the longest increasing subsequence. The philosophy that guides the exposition is that analysis of concrete problems is the most effective way to explain even the most general methods or abstract principles.

---

Table of contents :
Probability Theory and Combinatorial Optimization……Page 1
Contents……Page 8
Preface……Page 10
CHAPTER 1 First View of Problems and Methods……Page 12
CHAPTER 2 Concentration of Measure and the Classical Theorems……Page 38
CHAPTER 3 More General Methods……Page 64
CHAPTER 4 Probability in Greedy Algorithms and Linear Programming……Page 88
CHAPTER 5 Distributional Techniques and the Objective Method……Page 106
CHAPTER 6 Talagrand’s Isoperimetric Theory……Page 130
Bibliography……Page 154
Index……Page 168