FYI (Lecture Series)
Approximating the Permanent
Eric Vigoda
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
2015/3/11 Wed 9AM-10:15AM (E3-1, Room 1501)
I’ll explain the canonical paths method for bounding the mixing time of a
Markov chain. I’ll show the analysis of a Markov chain for generating a
random matching of a graph and its extension for the estimating the
number of perfect matchings of a bipartite graph.
Markov chain. I’ll show the analysis of a Markov chain for generating a
random matching of a graph and its extension for the estimating the
number of perfect matchings of a bipartite graph.