Books+ Search Results
Probability theory and combinatorial optimization
Author
Title
Probability theory and combinatorial optimization [electronic resource] / J. Michael Steele.
ISBN
9781611970029 (electronic bk.)
0898713803 (pbk.)
9780898713800 (pbk.)
Published
Philadelphia, Pa. : Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104), 1997.
Physical Description
1 electronic text (viii, 159 p.) : ill., digital file.
Local Notes
Access is available to the Yale community.
Notes
Title from title screen, viewed 04/05/2011.
Access and use
Access restricted by licensing agreement.
Summary
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. 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.
Variant and related titles
SIAM ebooks.
Other formats
Also available in print version.
Print version:
Format
Books / Online
Language
English
Added to Catalog
April 16, 2021
Series
CBMS-NSF regional conference series in applied mathematics ; 69
Bibliography
Includes bibliographical references (p. 143-155) and index.
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.
Publisher's number
CB69 SIAM
Subjects
Also listed under
Bookmark As
Citation
