Speaker: Ran Duan Max-Planck-Institut für Informatik
Time: 2014-04-08 10:00-2014-04-08 11:00
Venue: FIT 1-222

Abstract:

 The maximum cardinality and maximum weight matching problems can be solved in Õ(m√n) time, a bound that has resisted improvement despite decades of research. (Here m and n are the number of edges and vertices.) We demonstrate that this “m√n barrier” can be bypassed by approximation. For any ε > 0, we give an algorithm that computes a (1 − ε)-approximate maximum weight matching in O(mε^{−1} log ε^{−1}) time, that is, optimal linear time for any fixed ε. Our algorithm is dramatically simpler than the best exact maximum weight matching algorithms on general graphs and should be useful in applications that can tolerate a negligible relative error. This result has been published in JACM. 

 

We also give a new algorithm for exact bipartite maximum weight matching in O(m√n log N) time, which improves Gabow and Tarjan's result of O(m√n log(nN)) standing for more than 20 years.

Short Bio:

 Ran Duan received his B.S. degree in Computer Science at Tsinghua University in 2002, and his M.S. and Ph.D. degrees in Theoretical Computer Science at University of Michigan, Ann Arbor (under the instruction of Prof. Seth Pettie). Now, he is a postdoctoral researcher in Max-Planck-Institut für Informatik in Germany, supported by Alexander von Humboldt fellowship. His research interest focuses on graph algorithms, data structures, and algorithmic game theory.