An introduction to the state of the art of the probability theory most applicable to combinatorial optimization.Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.
Preface 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 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 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 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 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 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.
Preface 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 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 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 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 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 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.
Es gelten unsere Allgemeinen Geschäftsbedingungen: www.buecher.de/agb
Impressum
www.buecher.de ist ein Internetauftritt der buecher.de internetstores GmbH
Geschäftsführung: Monica Sawhney | Roland Kölbl | Günter Hilger
Sitz der Gesellschaft: Batheyer Straße 115 - 117, 58099 Hagen
Postanschrift: Bürgermeister-Wegele-Str. 12, 86167 Augsburg
Amtsgericht Hagen HRB 13257
Steuernummer: 321/neu
