Interdisciplinary Seminar Series

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


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.

DIMACS/CCICADA Interdisciplinary Series, Complete Calendar