Coverart for item
The Resource Randomized algorithms : approximation, generation, and counting, Russ Bubley

Randomized algorithms : approximation, generation, and counting, Russ Bubley

Label
Randomized algorithms : approximation, generation, and counting
Title
Randomized algorithms
Title remainder
approximation, generation, and counting
Statement of responsibility
Russ Bubley
Creator
Subject
Language
eng
Summary
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
Member of
Action
digitized
http://library.link/vocab/creatorDate
1974-
http://library.link/vocab/creatorName
Bubley, Russ
Dewey number
519.2/33
Illustrations
illustrations
Index
index present
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
Series statement
Distinguished dissertations,
http://library.link/vocab/subjectName
  • Markov processes
  • Monte Carlo method
  • Computational complexity
Label
Randomized algorithms : approximation, generation, and counting, Russ Bubley
Instantiates
Publication
Antecedent source
file reproduced from original
Bibliography note
Includes bibliographical references (pages 139-148) and index
Color
black and white
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
Control code
ocn680431066
Dimensions
unknown
Extent
1 online resource (xvi, 152 pages)
Form of item
online
Isbn
9781447111801
Level of compression
  • lossless
  • lossy
Note
SpringerLink
Other physical details
illustrations
Reformatting quality
  • preservation
  • access
Reproduction note
Electronic reproduction.
Specific material designation
remote
System control number
(OCoLC)680431066
System details
Master and use copy. Digital master created according to Benchmark for Faithful Digital Reproductions of Monographs and Serials, Version 1. Digital Library Federation, December 2002.
Label
Randomized algorithms : approximation, generation, and counting, Russ Bubley
Publication
Antecedent source
file reproduced from original
Bibliography note
Includes bibliographical references (pages 139-148) and index
Color
black and white
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
Control code
ocn680431066
Dimensions
unknown
Extent
1 online resource (xvi, 152 pages)
Form of item
online
Isbn
9781447111801
Level of compression
  • lossless
  • lossy
Note
SpringerLink
Other physical details
illustrations
Reformatting quality
  • preservation
  • access
Reproduction note
Electronic reproduction.
Specific material designation
remote
System control number
(OCoLC)680431066
System details
Master and use copy. Digital master created according to Benchmark for Faithful Digital Reproductions of Monographs and Serials, Version 1. Digital Library Federation, December 2002.

Library Locations

    • InternetBorrow it
      Albany, Auckland, 0632, NZ
Processing Feedback ...