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



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 oct28n 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

Your email address will not be published.


This site uses Akismet to reduce spam. Learn how your comment data is processed.