Computer Science/Discrete Mathematics Seminar I

Matching: A New Proof for an Ancient Algorithm

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.

Date & Time

December 10, 2012 | 11:15am – 12:15pm

Location

S-101

Speakers

Vijay Vazirani

Affiliation

Georgia Institute of Technology