Geschäftskunden Kundenprogramme
Vor Ort
Merkzettel Warenkorb
Randomized Algorithms: Approximation, Generation, and Counting

Randomized Algorithms: Approximation, Generation, and Counting

Aus der Reihe

Fr. 138.00

inkl. gesetzl. MwSt.
Versandkostenfrei
Taschenbuch

Taschenbuch

Fr. 138.00 eBook

eBook

Fr. 125.90

Randomized Algorithms: Approximation, Generation, and Counting

Ebenfalls verfügbar als:

Taschenbuch

Taschenbuch

ab Fr. 138.00
eBook

eBook

ab Fr. 125.90

Beschreibung

Details

Einband

Taschenbuch

Erscheinungsdatum

16.09.2011

Verlag

Springer London

Seitenzahl

152

Maße (L/B/H)

23.5/15.5/1 cm

Beschreibung

Details

Einband

Taschenbuch

Erscheinungsdatum

16.09.2011

Verlag

Springer London

Seitenzahl

152

Maße (L/B/H)

23.5/15.5/1 cm

Gewicht

277 g

Auflage

Softcover reprint of the original 1st ed. 2001

Sprache

Englisch

ISBN

978-1-4471-1180-1

Weitere Bände von Distinguished Dissertations

Unsere Kundinnen und Kunden meinen

0.0

0 Bewertungen

Informationen zu Bewertungen

Zur Abgabe einer Bewertung ist eine Anmeldung im Konto notwendig. Die Authentizität der Bewertungen wird von uns nicht überprüft. Wir behalten uns vor, Bewertungstexte, die unseren Richtlinien widersprechen, entsprechend zu kürzen oder zu löschen.

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kund*innen durch Ihre Meinung

Erste Bewertung verfassen

Unsere Kundinnen und Kunden meinen

0.0

0 Bewertungen filtern
  • Randomized Algorithms: Approximation, Generation, and Counting
  • 1 Mathematical Background.- 1.1 Computational Complexity.- 1.1.1 Introduction.- 1.1.2 Notation for Asymptotics: ?, ?, and ?.- 1.1.3 Complexity Classes.- 1.1.4 Oracles, Reductions, and Hardness.- 1.1.5 More Complexity Classes.- 1.1.6 Conclusion.- 1.1.7 Some Common Problems in Complexity Theory.- 1.2 Probability.- 1.3 Markov Chains.- 1.4 Graph Theory.- 1.4.1 Tutte—Gröthendieck Polynomial.- 1.4.2 Hypergraphs.- 2 Techniques for Sampling and Approximate Sampling.- 2.1 Introduction.- 2.1.1 Definitions.- 2.2 Direct Sampling.- 2.2.1 Monte Carlo Method: Rejection Sampling.- 2.2.2 Karp—Luby Technique.- 2.3 Markov Chain Method.- 2.3.1 Coupling.- 2.3.1.1 Maximal couplings.- 2.3.2 Dobrushin’s Uniqueness Criterion.- 2.3.3 Canonical Paths.- 2.3.4 Conductance.- 2.3.5 Comparison Methods.- 2.3.6 Other Methods.- 2.3.6.1 Poincaré-type inequalities.- 2.3.6.2 Logarithmic Sobolev inequalities.- 2.3.7 Coupling from the Past.- 3 Approximate Counting.- 3.1 Parsimonious Reductions.- 3.2 Counting Directly.- 3.2.1 Direct Sampling.- 3.2.2 Karp—Luby Technique.- 3.3 Counting and Sampling.- 3.4 The Markov Chain Monte Carlo Method.- 4 Applications: Coupling.- 4.1 Hypergraph Colourings.- 4.1.1 Introduction.- 4.1.1.1 Notation and preliminaries.- 4.1.2 Approximate Sampling.- 4.1.2.1 Computing the permutation.- 4.1.2.2 Rapidity of coupling.- 4.1.2.3 Two sufficient conditions.- A condition of k > ?1+?3.- A condition of k > 2?2.- 4.1.3 Almost uniform sampling for k=2?2.- 4.1.3 The Approximation Scheme.- 4.1.4 Conclusions.- 4.2 Sink-Free Graph Orientations and Twice-Sat.- 4.2.1 Introduction.- 4.2.1.1 Notation and preliminaries.- 4.2.1.2 Equivalence of Twice-Sat and SFO.- 4.2.2 Decision and Construction.- 4.2.3 Exact Counting.- 4.2.3.1 Self-reducibility.- 4.2.3.2 Relationship to counting independent sets.- 4.2.3.3 #P-completeness of #SFO.- 4.2.4 Approximate Sampling.- 4.2.5 The Approximation Scheme.- 4.2.6 Conclusions.- 4.3 Log-Concave Sampling, and the Volume of a Convex Body.- 4.3.1 Introduction.- 4.3.2 Background and Preliminaries.- 4.3.2.1 Convex bodies and gauge functions.- 4.3.2.2 Sampling equivalence.- 4.3.2.3 Modifying FK.- 4.3.2.4 Metropolis random walks.- 4.3.2.5 The random walk.- 4.3.2.6 Coupling.- 4.3.2.7 Technical results.- 4.3.3 Analysis of the Random Walk.- 4.3.3.1 Boundedness of the walk.- 4.3.3.2 Bringing the random walks close.- 4.3.3.3 Making the random walks meet.- 4.3.4 Improvements.- 4.3.4.1 A faster simulation of the random walk.- 4.3.4.2 An even faster simulation.- 4.3.5 Conclusions.- Intermezzo: Path Coupling.- 5 Applications: Path Coupling.- 5.1 Introduction.- 5.2 Twice-Sat Revisited.- 5.3 Sink- and Source-Free Graph Orientations.- 5.3.1 Introduction.- 5.3.2 Decision and Construction.- 5.3.3 Exact Counting.- 5.3.3.1 Self-reducibility.- 5.3.3.2 #P-completeness of #SSFO.- 5.3.4 Approximate Counting and Sampling.- 5.4 Totally Edge Cyclic Orientations.- 5.4.1 Approximate Sampling.- 5.5 Independent Sets: The Conserved Hard-Core Model.- 5.5.1 #P-Completeness of Exact Counting.- 5.5.2 Approximate Sampling.- 5.6 Independent Sets: The Non-Conserved Hard-Core Model.- 5.6.1 Approximate Counting.- 5.7 Linear Extensions of a Partial Order.- 5.7.1 Introduction.- 5.7.2 Notation and Preliminaries.- 5.7.3 The Coupling.- 5.7.4 Lower Bounds and Related Chains.- 5.7.5 Conclusions.- 5.8 Graph Colouring.- 5.9 The Extended Potts Framework.- 5.10 Graph Colouring Revisited.- 5.10.1 #P-Completeness.- 5.10.2 Approximate Sampling.- 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.