Probability Theory and Combinatorial OptimizationThis 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. 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. The third and deepest theme developed here concerns the application of Talagrand's isoperimetric theory of concentration inequalities. |
Other editions - View all
Common terms and phrases
additional algorithm analysis applied argument assignment problem Azuma’s inequality basic behavior bound called central chapter choice choose closely combinatorial combinatorial optimization complete computation concentration condition connected consider considerable constant contains convergence cost define definition denote depend developed difference distance easily easy edge equal example expected expression fact Finally find finite first function further geometric give given graph heuristic idea increasing independent inequality integer least lemma length limit longest matching mean measure method minimal monotonicity natural objective obtained optimal partition points Poisson probability problem proof prove random variables result sample satisfies sequence solution space-filling curve spanning tree square step subadditivity subsequence Suppose Talagrand’s technique tells theorem theory tour uniform uniformly distributed unit vertex write