Markov Chain Monte Carlo and Approximating the Permanent

Eric Vigoda

College of Computing, Georgia Institute of Technology, Atlanta, USA

College of Computing, Georgia Institute of Technology, Atlanta, USA

2009/04/13

**Monday 5PM-6PM**The Markov Chain Monte Carlo (MCMC) method is a widely-used algorithmic approach for randomly sampling from and estimating the cardinality of large sets. In this talk I will give an introduction to the MCMC approach. Then I will explain a more sophisticated variant that gives a polynomial-time algorithm to approximate the permanent of a non-negative matrix. In graph-theoretic terminology, the permanent corresponds to the number of perfect matchings of a bipartite graph.

Tags: EricVigoda