Approximate Counting
Lists
Only you see this
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...