Cover Image

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 co...

Full description

Bibliographic Details
Main Author: Bubley, Russ, 1974-
Corporate Author: SpringerLink (Online service)
Format: eBook
Language:English
Published: London ; New York : Springer, 2001.
Series:CPHC/BCS distinguished dissertations.
Subjects:
Markov processes.
Monte Carlo method.
Computational complexity.
Markov, Processus de.
Monte-Carlo, Méthode de.
Complexité de calcul (Informatique)
Markov-Ketten-Monte-Carlo-Verfahren.
Graphentheorie.
Randomisierter Algorithmus.
Algebra > Data processing.
Combinatorial analysis.
Computer science.
Computer software.
Distribution (Probability theory)
Electronic books.
Online Access:Connect to the full text of this electronic book
Table of Contents:
  • Mathematical Background
  • Techniques for Sampling and Approximate Sampling
  • Approximate Counting
  • Applications: Coupling
  • Intermezzo: Path Coupling
  • Applications: Path Coupling
  • Directions for Future Work
  • Appendix A: An Application of Dobrushin's Uniqueness Criterion
  • Appendix B: A Hierarchy of #Sat Restrictions
  • Appendix C: Equivalence of Transposition Distance To Spearman's Footrule
  • Bibliography
  • Index.