Vijay V. Vazirani
Georgia Institute of Technology
Date: Friday, January 4th, 2013
Time: 3 PM
Venue: CS101.
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.
Vijay V. Vazirani received his B.S. degree from Massachusetts Institute of Technology in 1979 and Ph.D. from the University of California, Berkeley in 1983. He is currently a professor at the College of Computing at Georgia Institute of Technology. His research interests are on algorithmic problems in mathematical economics and game theory, design of efficient exact and approximation algorithms, and computational complexity theory.