Skip to main content
SpringerLink
Log in
Birkhäuser

Counting, Sampling and Integrating: Algorithms and Complexity

  • Book
  • © 2003

Overview

Authors:
  1. Mark Jerrum

    1. Division of Informatics, The University of Edinburgh, Edinburgh, Scotland, UK

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • ETH lecture notes based on a course held in summer 2000
  • Unique collection of material

Part of the book series: Lectures in Mathematics. ETH Zürich (LM)

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 64.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 84.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-xi
    Download chapter PDF

  2. Two good counting algorithms

    • Mark Jerrum
    Pages 1-10

  3. #P-completeness

    • Mark Jerrum
    Pages 11-23

  4. Sampling and counting

    • Mark Jerrum
    Pages 25-32

  5. Coupling and colourings

    • Mark Jerrum
    Pages 33-47

  6. Canonical paths and matchings

    • Mark Jerrum
    Pages 49-64

  7. Volume of a convex body

    • Mark Jerrum
    Pages 65-92

  8. Inapproximability

    • Mark Jerrum
    Pages 93-103

  9. Back Matter

    Pages 105-112
    Download chapter PDF
Back to top

Keywords

About this book

These notes had their origin in a postgraduate lecture series I gave at the Eid­ genossiche Technische Hochschule (ETH) in Zurich in the Spring of 2000. I am very grateful to my hosts, the Forschungsinstitut fUr Mathematik at ETH, for providing the ideal opportunity to develop and present this material in what I hope is a reasonably coherent manner, and also for encouraging and assisting me to record the proceedings in these lecture notes. The subject of the lecture series was counting (of combinatorial structures) and related topics, viewed from a computational perspective. As we shall see, "related topics" include sampling combinatorial structures (being computationally equivalent to approximate counting via efficient reductions), evaluating partition functions (being weighted counting) and calculating the volume of bodies (being counting in the limit). We shall be inhabiting a different world to the one conjured up by books with titles like Combinatorial Enumeration or Graphical Enumeration. There, the prob­ lems are usually parameterised on a single integer parameter n, and the required solutions are closed form or asymptotic estimates obtained using very refined and precise analytical tools.

Authors and Affiliations

  • Division of Informatics, The University of Edinburgh, Edinburgh, Scotland, UK

    Mark Jerrum

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation