Algorithms and Complexity Seminar
Approximate Weighted Matching in Linear Time
Seth Pettie (University of Michigan)
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.