Title :
Markov chains and polynomial time algorithms
Author_Institution :
Dept. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA
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 :
Markov processes; computational complexity; randomised algorithms; Markov Chains; approximately certain; counting problems; perfect matchings; polynomial time algorithms; randomized algorithms; Approximation algorithms; Computer science; Convergence; Lattices; Polynomials; Sampling methods; Steady-state; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Conference_Location :
Santa Fe, NM
Print_ISBN :
0-8186-6580-7
DOI :
10.1109/SFCS.1994.365726
