Cantitate/Preț
Produs

Randomized Algorithms: Approximation, Generation, and Counting: Distinguished Dissertations

Autor Russ Bubley
en Limba Engleză Paperback – 16 sep 2011
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.
Citește tot Restrânge

Din seria Distinguished Dissertations

Preț: 63952 lei

Preț vechi: 79941 lei
-20% Nou

Puncte Express: 959

Preț estimativ în valută:
12239 12626$ 10358£

Carte tipărită la comandă

Livrare economică 05-19 martie

Preluare comenzi: 021 569.72.76

Specificații

ISBN-13: 9781447111801
ISBN-10: 144711180X
Pagini: 176
Ilustrații: XX, 152 p.
Dimensiuni: 155 x 235 x 9 mm
Greutate: 0.25 kg
Ediția:Softcover reprint of the original 1st ed. 2001
Editura: SPRINGER LONDON
Colecția Springer
Seria Distinguished Dissertations

Locul publicării:London, United Kingdom

Public țintă

Research

Cuprins

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.