[size=-1]Contents 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. 1997 / viii + 159 pages / Softcover / ISBN-13: 978-0-898713-80-0 / ISBN-10: 0-89871-380-3 / List Price $48.00 / SIAM/CBMS Member Price $33.60 / Order Code CB69

[size=-1]Price