Approximate Counting

Rajeev Motwani, Prabhakar RaghavanCambridge 1995 · DOI · OpenAlex

Abstract

IN this chapter we apply randomization to hard counting problems. After defining the class #P, we present several #P-complete problems. We present a (randomized) polynomial time approximation scheme for the problem of counting the number of satisfying truth assignments for a DNF formula. The problem of approximate counting of perfect matchings in a bipartite graph is shown to be reducible to that of the uniform generation of perfect matchings. We describe a solution to the latter problem using the rapid mixing property of a suitably defined random walk, provided the input graph is sufficiently dense. We conclude with an overview of the estimation of the volume of a convex body.
BibTeX
@inproceedings{motwani1995approximate,
  author = {Rajeev Motwani and Prabhakar Raghavan},
  title = {{Approximate Counting}},
  booktitle = {Cambridge},
  year = {1995},
  doi = {10.1017/cbo9780511814075.012},
}

Loading related content...

Figure