Colloquium
Seth Pettie
University of Michigan
Friday, March 2, 2012
3147 MEB
Refreshments 3:20 p.m.
Lecture 3:40 p.m.
Host: Suresh Venkatasubramanian
Title: Approximating Maximum Weight Matching in Linear Time
Seth Pettie
University of Michigan
Friday, March 2, 2012
3147 MEB
Refreshments 3:20 p.m.
Lecture 3:40 p.m.
Host: Suresh Venkatasubramanian
Title: Approximating Maximum Weight Matching in Linear Time
Abstract
It has been known for some time that the textbook problems of finding a maximum weight matching (MWM) or maximum cardinality matching (MCM) can be solved in O~(m n^{1/2}) time, where m and n are the number of edges and vertices in the graph. However, the complexity of the approximate MWM problem remained open. In this talk I'll present a simple (1-eps)-approximate MWM algorithm running in (linear) O(m (1/eps)log(1/eps)) time, for any eps>0. This is the first linear-time (1-eps)-approximate algorithm, which improves on several slower algorithms with approximation ratios 2/3, 3/4, and 4/5. This is joint work with Ran Duan, and can be found here. A preliminary version of this result appeared in FOCS 2010.
BIO
Dr. Pettie is a professor of Electrical Engineering and Computer Science at the University of Michigan. He received his Ph.D. from the University of Texas at Austin in 2003 and was a researcher at the Max Planck Institute for Computer Science, from 2003-2006. He has elite frequent flyer status on multiple major US carriers.
It has been known for some time that the textbook problems of finding a maximum weight matching (MWM) or maximum cardinality matching (MCM) can be solved in O~(m n^{1/2}) time, where m and n are the number of edges and vertices in the graph. However, the complexity of the approximate MWM problem remained open. In this talk I'll present a simple (1-eps)-approximate MWM algorithm running in (linear) O(m (1/eps)log(1/eps)) time, for any eps>0. This is the first linear-time (1-eps)-approximate algorithm, which improves on several slower algorithms with approximation ratios 2/3, 3/4, and 4/5. This is joint work with Ran Duan, and can be found here. A preliminary version of this result appeared in FOCS 2010.
BIO
Dr. Pettie is a professor of Electrical Engineering and Computer Science at the University of Michigan. He received his Ph.D. from the University of Texas at Austin in 2003 and was a researcher at the Max Planck Institute for Computer Science, from 2003-2006. He has elite frequent flyer status on multiple major US carriers.