Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series - Tuesday, October 28, 2014

Linda Casals lindac at
Mon Oct 27 14:25:30 EDT 2014


DIMACS/CCICADA Interdisciplinary Seminar Series Presents

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 Full Calendar

More information about the Dimacs-ccicada-announce mailing list