Campus Event Calendar
Event Entry
What and Who
Dispelling an Old Myth about an Ancient Algorithm
Vijay V. Vazirani
Georgia Tech
MPI Colloquium Series Distinguished Speaker
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 17 August 2012
14:00
90 Minutes
E1 4
024
Saarbrücken
Abstract
Title: Dispelling an Old Myth about an Ancient Algorithm
Speaker: Vijay V. Vazirani, Georgia Tech
Abstract:
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: Vijay V. Vazirani, Georgia Tech
Abstract:
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
Contact
Kurt Mehlhorn
--email hidden
passcode not visible
logged in users only
Kurt Mehlhorn, 08/08/2012 12:18 -- Created document.