Probability Theory and Combinatorial Optimization

Preface; 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; 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; 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; 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; 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; Dénoument; Central limit theory; Conditioning method for independence; Dependency graphs and the CLT; Additional remarks; 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.