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 dimacs.rutgers.edu
Tue Oct 21 15:23:37 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 

*********************************************************************
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 Full Calendar
See: http://dimacs.rutgers.edu/Seminars/interseminars14-15.html
_______________________________________________



More information about the Dimacs-ccicada-announce mailing list