Title: Approximating Maximum Weight Matching in Linear Time
Speaker: Seth Pettie, University of Michigan
Date: Tuesday, October 28, 2014 12:00 - 1:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Seminar hosted by James Abello, DIMACS
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.