- Series
- ACO Seminar
- Time
- Monday, February 11, 2013 - 4:00pm for 1.5 hours (actually 80 minutes)
- Location
- Klaus 1116 W
- Speaker
- Vijay V. Vazirani – School of Computer Science, Georgia Tech
- Organizer
For all practical purposes, the Micali-Vazirani algorithm, discovered in
1980, is still the most efficient known maximum matching algorithm (for
very dense graphs, slight asymptotic improvement can be obtained using
fast matrix multiplication). However, this has remained a "black box"
result for the last 32 years. We hope to change this with the help of a
recent paper giving a simpler proof and exposition of the algorithm:
http://arxiv.org/abs/1210.4594
In the interest of covering all the ideas, we will assume that the
audience is familiar with basic notions such as augmenting paths and
bipartite matching algorithm.