Skip to main content
SpringerLink
Log in
Book cover

Randomized Algorithms: Approximation, Generation, and Counting

  • Book
  • © 2001

Overview

Authors:
  1. Russ Bubley

    1. University of Leeds, Leeds, UK

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Distinguished Dissertations (DISTDISS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (7 chapters)

  1. Front Matter

    Pages i-xix
    Download chapter PDF

  2. Mathematical Background

    • Russ Bubley
    Pages 1-11

  3. Techniques for Sampling and Approximate Sampling

    • Russ Bubley
    Pages 13-28

  4. Approximate Counting

    • Russ Bubley
    Pages 29-36

  5. Applications: Coupling

    • Russ Bubley
    Pages 37-82

  6. Intermezzo

    • Russ Bubley
    Pages 83-90

  7. Applications: Path Coupling

    • Russ Bubley
    Pages 91-118

  8. Directions for Future Work

    • Russ Bubley
    Pages 119-124

  9. Back Matter

    Pages 139-152
    Download chapter PDF
Back to top

Keywords

About this book

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.

Authors and Affiliations

  • University of Leeds, Leeds, UK

    Russ Bubley

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation