Markov chains and polynomial time algorithms
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 656-671
- https://doi.org/10.1109/sfcs.1994.365726
Abstract
This paper outlines the use of rapidly mixing Markov Chains in randomized polynomial time algorithms to solve approximately certain counting problems. They fall into two classes: combinatorial problems like counting the number of perfect matchings in certain graphs and geometric ones like computing the volumes of convex sets.Keywords
This publication has 52 references indexed in Scilit:
- Sampling from Log-Concave DistributionsThe Annals of Applied Probability, 1994
- A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack ProblemCombinatorics, Probability and Computing, 1993
- Balanced matroidsPublished by Association for Computing Machinery (ACM) ,1992
- Generating a Random Linear Extension of a Partial OrderThe Annals of Probability, 1991
- Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion ProcessThe Annals of Applied Probability, 1991
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- On coupling and the approximation of the permanentInformation Processing Letters, 1989
- A geometric inequality and the complexity of computing volumeDiscrete & Computational Geometry, 1986
- An optimal Poincaré inequality for convex domainsArchive for Rational Mechanics and Analysis, 1960
- Equation of State Calculations by Fast Computing MachinesThe Journal of Chemical Physics, 1953