CSAIL Event Calendar: Previous Series

[A&C seminar] Approximate Weighted Matching in Linear Time

Speaker: Seth Pettie , University of Michigan
Date: February 28 2011
Time: 4:00PM to 5:10PM
Location: G575
Contact: Aleksander Madry, madry@mit.edu
Relevant URL: http://people.csail.mit.edu/madry/algcompsem/

Given a weighted graph, the maximum weight matching problem (MWM) is to find a set of vertex-disjoint edges with maximum weight. In the 1960s Edmonds showed that MWMs can be found in polynomial time. At present the fastest MWM algorithm, due to Gabow and Tarjan, runs in roughly $O~(m\sqrt{n})$ time, where $m$ and $n$ are the number of edges and vertices in the graph. Surprisingly, restricted versions of the problem, such as computing $(1-\eps)$-approximate MWMs or finding maximum cardinality matchings, are not known to be much easier. The best algorithms for these problems also run in $O~(m\sqrt{n})$ time.

In this paper we present the first linear time algorithm for computing a $(1-\eps)$-approximate MWM. Specifically, given an arbitrary real-weighted graph any $\eps>0$, our algorithm computes such a matching in $O(m poly(1/eps))$ time. The previous best approximate MWM algorithm with comparable running time could only guarantee a $(2/3-\epsilon)$-approximate solution.

See other events that are part of

See other events happening in February 2011