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

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.

DIMACS/CCICADA
Interdisciplinary Series, Complete Calendar