Probability Theory and Combinatorial Optimization
Society for Industrial & Applied Mathematics,U.S. (Verlag)
978-0-89871-380-0 (ISBN)
This monograph provides an introduction to the state of the art of the probability theory that is most directly applicable to combinatorial optimization. Much attention is paid to those questions dealing 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.
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.
| Erscheint lt. Verlag | 31.12.1997 |
|---|---|
| Reihe/Serie | CBMS-NSF Regional Conference Series in Applied Mathematics |
| Verlagsort | New York |
| Sprache | englisch |
| Maße | 152 x 229 mm |
| Gewicht | 317 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Angewandte Mathematik |
| Mathematik / Informatik ► Mathematik ► Graphentheorie | |
| Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
| ISBN-10 | 0-89871-380-3 / 0898713803 |
| ISBN-13 | 978-0-89871-380-0 / 9780898713800 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
