Matching: A New Proof for an Ancient Algorithm

Computer Science/Discrete Mathematics Seminar I
Topic:Matching: A New Proof for an Ancient Algorithm
Speaker:Vijay Vazirani
Affiliation:Georgia Institute of Technology
Date:Monday, December 10
Time/Room:11:15am - 12:15pm/S-101

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.