Dispelling an Old Myth about an Ancient Algorithm

Myth – and grapevine – has it that the Micali-Vazirani maximum matching algorithm is “too complicated”. The purpose of this talk is to show the stunningly beautiful structure of minimum length alternating paths and to convince the audience that our algorithm exploits this structure in such a simple and natural manner that the entire algorithm can fit into one’s mind as a single thought.

For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication). Yet, no more than a handful of people have understood this algorithm; we hope to change this.

Based on the following two papers:

http://www.cc.gatech.edu/~vazirani/MV.pdf

http://www.cc.gatech.edu/~vazirani/Theory-of-matching.pdf

Speaker Details

Vijay Vazirani got his Bachelor’s degree in Computer Science from MIT in 1979 and his Ph.D. from the University of California at Berkeley in 1983. His research career has been centered around the design of algorithms. During the 1980s, he made seminal contributions to the classical maximum matching problem and worked on the use of randomization for obtaining efficient algorithms as well as for proving computational intractability. During the 1990s he obtained approximation algorithms for several fundamental NP-hard optimization problems. And in the new millennium, he has worked extensively on understanding the computability of market equilibria.

In 2001 he published what was widely regarded as the definitive book on Approximation Algorithms. This book has been translated into Japanese, Polish, French and Chinese. In 2007 he co-edited a comprehensive volume on Algorithmic Game Theory. In 2011 he was inducted a Guggenheim Fellow, and he was a Distinguished SISL Visitor at the Social and Information Sciences Laboratory at Caltech during 2011-12.

Series:
Microsoft Research Talks
Date:
Speakers:
Vijay Vazirani

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks