DocumentCode :
2780427
Title :
The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume
Author :
Lovász, László ; Simonovits, Miklós
Author_Institution :
Eotvos Lorand Univ., Budapest, Hungary
fYear :
1990
fDate :
22-24 Oct 1990
Firstpage :
346
Abstract :
A. Sinclair and M. Jerrum (1988) derived a bound on the mixing rate of time-reversible Markov chains in terms of their conductance. The authors generalize this result by not assuming time reversibility and using a weaker notion of conductance. They prove an isoperimetric inequality for subsets of a convex body. These results are combined to simplify an algorithm of M. Dyer et al. (1989) for approximating the volume of a convex body and to improve running-time bounds
Keywords :
Markov processes; computational geometry; Markov chains; conductance; convex body; isoperimetric inequality; mixing rate; running-time; time-reversible; Algorithm design and analysis; Lattices; Law; Legal factors; Polynomials; Testing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
Type :
conf
DOI :
10.1109/FSCS.1990.89553
Filename :
89553
Link To Document :
بازگشت