Seminar Series: Approximating Maximum Weight Matching in Linear Time, October 28, 2014
Interdisciplinary Series, Tuesday, October 28, 2014 12:00 – 1:00pm
Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Title: Approximating Maximum Weight Matching in Linear Time
Speaker: Seth Pettie, University of Michigan
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~(mn^{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 MWM algorithm, which improves on several 2/3-approximate MWM algorithms.
Ref: Ran Duan and Seth Pettie, J. ACM 61(1):1, 2014.
Leave a comment