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.

Tags: EricVigoda