Information Science and Technology Seminar

Wednesday April 25, 2012 4:00 PM

Dispelling an Old Myth about an Ancient Algorithm

Speaker: Vijay Vazirani, College of Computing, Georgia Tech
Location: Annenberg 105
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. <br><br> 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. <br><br> Based on the following two papers: http://www.cc.gatech.edu/~vazirani/MV.pdf <br><br> http://www.cc.gatech.edu/~vazirani/Theory-of-matching.pdf
Series Information Science and Technology Seminar

Contact: Sydney Garstang at x4555 sydney@caltech.edu