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.
