Randomized Algorithms: Approximation, Generation, and Counting

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.

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.