Skip to main content
SpringerLink
Log in

Probabilistic Methods for Algorithmic Discrete Mathematics

  • Book
  • © 1998

Overview

Editors:
  1. Michel Habib

    1. LIRMM, Montpellier Cedex 5, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Colin McDiarmid

    1. Department of Statistics, University of Oxford, Oxford, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Jorge Ramirez-Alfonsin

    1. Equipe Combinatoire, Université Pierre et Marie Curie, Paris 6 Case 189, Paris Cedex 5, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Bruce Reed

    1. Equipe Combinatoire, Université Pierre et Marie Curie, Paris 6 Case 189, Paris Cedex 5, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Probabilistic methods belong to the hottest topics in combinatorics and the theory of algorithms

Part of the book series: Algorithms and Combinatorics (AC, volume 16)

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
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover 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-XVII
    Download chapter PDF

  2. The Probabilistic Method

    • Michael Molloy
    Pages 1-35

  3. Probabilistic Analysis of Algorithms

    • Alan M. Frieze, Bruce Reed
    Pages 36-92

  4. An Overview of Randomized Algorithms

    • Rajeev Motwani, Prabhakar Raghavan
    Pages 93-115

  5. Mathematical Foundations of the Markov Chain Monte Carlo Method

    • Mark Jerrum
    Pages 116-165

  6. Percolation and the Random Cluster Model: Combinatorial and Algorithmic Problems

    • Dominic Welsh
    Pages 166-194

  7. Concentration

    • Colin McDiarmid
    Pages 195-248

  8. Branching Processes and Their Applications in the Analysis of Tree Structures and Tree Algorithms

    • Luc Devroye
    Pages 249-314

  9. Back Matter

    Pages 315-325
    Download chapter PDF
Back to top

Keywords

About this book

Leave nothing to chance. This cliche embodies the common belief that ran­ domness has no place in carefully planned methodologies, every step should be spelled out, each i dotted and each t crossed. In discrete mathematics at least, nothing could be further from the truth. Introducing random choices into algorithms can improve their performance. The application of proba­ bilistic tools has led to the resolution of combinatorial problems which had resisted attack for decades. The chapters in this volume explore and celebrate this fact. Our intention was to bring together, for the first time, accessible discus­ sions of the disparate ways in which probabilistic ideas are enriching discrete mathematics. These discussions are aimed at mathematicians with a good combinatorial background but require only a passing acquaintance with the basic definitions in probability (e.g. expected value, conditional probability). A reader who already has a firm grasp on the area will be interested in the original research, novel syntheses, and discussions of ongoing developments scattered throughout the book. Some of the most convincing demonstrations of the power of these tech­ niques are randomized algorithms for estimating quantities which are hard to compute exactly. One example is the randomized algorithm of Dyer, Frieze and Kannan for estimating the volume of a polyhedron. To illustrate these techniques, we consider a simple related problem. Suppose S is some region of the unit square defined by a system of polynomial inequalities: Pi (x. y) ~ o.

Editors and Affiliations

  • LIRMM, Montpellier Cedex 5, France

    Michel Habib

  • Department of Statistics, University of Oxford, Oxford, UK

    Colin McDiarmid

  • Equipe Combinatoire, Université Pierre et Marie Curie, Paris 6 Case 189, Paris Cedex 5, France

    Jorge Ramirez-Alfonsin, Bruce Reed

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation