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; Dénoument; 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.