This monograph provides an introduction to the state of the art of the probability theory that is most directly applicable to combinatorial optimization. The questions that receive the most attention are those that deal with discrete optimization problems for points in Euclidean space, such as the minimum spanning tree, the traveling-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. The philosophy that guides the exposition is that analysis of concrete problems is the most effective way to explain even the most general methods or abstract principles.
There are three fundamental probabilistic themes that are examined through our concrete investigations. First, there is a systematic exploitation of martingales. Over the last ten years, 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 flavors, ranging from the naïve 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. This new theory is reshaping almost everything 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 will find considerable coaching on how to use some of the most important ideas from that theory. Audience Researchers in optimization and applied probability will benefit from this book, as will students familiar with probability and optimization theory.
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.
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.
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.
Assignment problem; Simplex method for theoreticians; Dyer-Frieze-McDiarmid inequality; Dealing with integral constraints; Distributional bounds; Back to the future.
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.
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.
When you buy via the Amazon Listing there is good news and bad news. The good news is that you can get a package deal with The Cauchy-Schwarz Master Class. The bad news is Amazon sometimes let is run out of stock --- most recently, it has been IN STOCK.
Still, if Amazon can't promise quick delivery, then it is best to order through the SIAM listing. They are the publishers and they always have copies on hand. [Ordering details: List Price $41.50 / SIAM/CBMS Member Price $29.05 / Order Code CB69 1997 / viii + 159 pages paperback.]
Finally, the numbers ISBN-13: 978-0-898713-80-0 and ISBN-10: 0-89871-380-3 are useful if you need to hunt for a second hand copy, and, archaic though the institution may be, there is always the library: QA273.45.S74 1997
To do list: I plan to post the references from the book one of these days. The references to the older subadditivity results are otherwise hard to find.