Preface |
First View of Problems and Methods / Chapter 1: |
A first example: Long common subsequences |
Subadditivity and expected values |
AzumaG++s inequality and a first application |
A second example: The increasing-subsequence problem |
Flipping AzumaG++s inequality |
Concentration on rates |
Dynamic programming |
KingmanG++s subadditive ergodic theorem |
Observations on subadditive subsequences |
Additional notes |
Concentration of Measure and the Classical Theorems / Chapter 2: |
The TSP and quick application of AzumaG++s inequality |
Easy size bounds |
Another mean Poissonization |
The Beardwood-Halton-Hammersly theorem |
KarpG++s partitioning algorithms |
Introduction to space-filling curve heuristic |
Asymptotics for the space-filling curve heuristic |
More General Methods / Chapter 3: |
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 |
Probability in Greedy Algorithms and Linear Programming / Chapter 4: |
Assignment problem |
Simplex method for theoreticians |
Dyer-Frieze-McDiarmid inequality |
Dealing with integral constraints |
Distributional bounds |
Back to the future |
Distributional Techniques and the Objective Method / Chapter 5: |
Motivation for a method |
Searching for a candidate object |
Topology for nice sets |
Information on the infinite tree |
D+1/4noument |
Central limit theory |
Conditioning method for independence |
Dependency graphs and the CLT |
TalagrandG++s Isoperimetric Theory / Chapter 6: |
TalagrandG++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 TalagrandG++s isoperimetric inequalities |
Final considerations on related work |
Bibliography |
Index |
Preface |
First View of Problems and Methods / Chapter 1: |
A first example: Long common subsequences |