Randomized Algorithms: Approximation, Generation, and Counting
Published on 16. September 2011
Book
Paperback/Softback
XX, 152 pages
978-1-4471-1180-1 (ISBN)
Description
Randomized Algorithms
discusses two problems of fine pedigree: counting and generation, both of which are of fundamental importance to discrete mathematics and probability. When asking questions like "How many are there?" and "What does it look like on average?" of families of combinatorial structures, answers are often difficult to find -- we can be blocked by seemingly intractable algorithms.
Randomized Algorithms
shows how to get around the problem of intractability with the Markov chain Monte Carlo method, as well as highlighting the method's natural limits. It uses the technique of coupling before introducing "path coupling" a new technique which radically simplifies and improves upon previous methods in the area.
More details
Series
Edition
Softcover reprint of the original 1st ed. 2001
Language
English
Place of publication
London
United Kingdom
Target group
Professional and scholarly
Research
Illustrations
XX, 152 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 10 mm
Weight
277 gr
ISBN-13
978-1-4471-1180-1 (9781447111801)
DOI
10.1007/978-1-4471-0695-1
Schweitzer Classification
Other editions
Additional editions
E-Book
12/2012
Springer
€96.29
Available for download
Book
11/2000
Springer
€85.55
Article exhausted; check different version
Content
1 Mathematical Background.- 1.1 Computational Complexity.- 1.2 Probability.- 1.3 Markov Chains.- 1.4 Graph Theory.- 2 Techniques for Sampling and Approximate Sampling.- 2.1 Introduction.- 2.2 Direct Sampling.- 2.3 Markov Chain Method.- 3 Approximate Counting.- 3.1 Parsimonious Reductions.- 3.2 Counting Directly.- 3.3 Counting and Sampling.- 3.4 The Markov Chain Monte Carlo Method.- 4 Applications: Coupling.- 4.1 Hypergraph Colourings.- 4.2 Sink-Free Graph Orientations and Twice-Sat.- 4.3 Log-Concave Sampling, and the Volume of a Convex Body.- Intermezzo: Path Coupling.- 5 Applications: Path Coupling.- 5.1 Introduction.- 5.2 Twice-Sat Revisited.- 5.3 Sink- and Source-Free Graph Orientations.- 5.4 Totally Edge Cyclic Orientations.- 5.5 Independent Sets: The Conserved Hard-Core Model.- 5.6 Independent Sets: The Non-Conserved Hard-Core Model.- 5.7 Linear Extensions of a Partial Order.- 5.8 Graph Colouring.- 5.9 The Extended Potts Framework.- 5.10 Graph Colouring Revisited.- 6 Directions for Future Work.- 6.1 Breaking Thresholds.- 6.2 Beyond Self-Reducibility.- 6.3 Mixed Methods for Approximate Counting.- 6.4 Faster Reductions from Approximate Counting to Approximate Sampling.- 6.5 Anti-ferromagnetic Models.- 6.6 Log-Concave Sampling via Path Coupling.- Appendices.- A An Application of Dobrushin's Uniqueness Criterion.- B A Hierarchy of #SAT Restrictions.- B.1 Introduction.- B.2 A Summary of Known Results.- B.2.1 Easy Exact Counting.- B.2.2 Hard Exact Counting.- B.2.3 Easy Approximate Counting.- B.2.4 Hard Approximate Counting.- B.3 Summary and Conclusions.- C Equivalence of Transposition Distance to Spearman's Footrule.