This monograph provides an introduction to the state of the art of the probability theory that is most directly applicable to combinatorial optimization. Much attention is paid to those questions dealing with discrete optimization problems for points in Euclidean space, such as the minimum spanning tree, the travelling-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. There are three fundamental probabilistic themes that are examined through our concrete investigations. First, there is a systematic exploration of martingales. Many investigators of problems of combinatorial optimization have come to count on martingale inequalities as versatile tools which let us show that many of the naturally occurring random variables of combinatorial optimization are sharply concentrated about their means - a phenomenon with numerous practical and theoretical consequences. The second theme that is explored is the systematic use of subadditivity of several flavours, ranging from the naive subadditivity of real sequences to the subtler subadditivity of stochastic processes. By and large, subadditivity offers only elementary tools, but on remarkably many occasions such tools provide the key organizing principle in the attack on problems of nearly intractable difficulty. The third and deepest theme developed here concerns the application of Talagrand's isoperimetric theory of concentration inequalities which has affected much that is known in the probability theory of combinatorial optimization. The treatment given here deals with only a small part of Talagrand's theory, but the reader should find considerable coaching on how to use some of the most important ideas from that theory.
Preface Chapter 1: First View of Problems and Methods. A first example: Long common subsequences Subadditivity and expected values Azuma's inequality and a first application A second example: The increasing-subsequence problem Flipping Azuma's inequality Concentration on rates Dynamic programming Kingman's subadditive ergodic theorem Observations on subadditive subsequences Additional notes Chapter 2: Concentration of Measure and the Classical Theorems. The TSP and quick application of Azuma's inequality Easy size bounds Another mean Poissonization The Beardwood-Halton-Hammersly theorem Karp's partitioning algorithms Introduction to space-filling curve heuristic Asymptotics for the space-filling curve heuristic Additional notes Chapter 3: More General Methods. Subadditive Euclidean functionals Examples: Good, bad and forthcoming A general L-(infinity) bound Simple subadditivity and geometric subadditivity A concentration inequality Minimal matching Two-sided bounds and first consequences Rooted duals and their applications Lower bounds and best possibilities Additional remarks Chapter 4: Probability in Greedy Algorithms and Linear Programming. Assignment problem Simplex method for theoreticians Dyer-Frieze-McDiarmid inequality Dealing with integral constraints Distributional bounds Back to the future Additional remarks Chapter 5: Distributional Techniques and the Objective Method. Motivation for a method Searching for a candidate object Topology for nice sets Information on the infinite tree Denoument Central limit theory Conditioning method for independence Dependency graphs and the CLT Additional remarks Chapter 6: Talagrand's Isoperimetric Theory. Talagrand's isoperimetric theory Two geometric applications of the isoperimetric inequality Application to the longest-increasing-subsequence problem Proof of the isoperimetric problem Application and comparison in the theory of hereditary sets Suprema of linear functionals Tail of the assignment problem Further applications of Talagrand's isoperimetric inequalities Final considerations on related work Bibliography Index.
