Scaling algorithms for approximate and exact maximum weight matching

Understand

The {\em maximum cardinality} and {\em maximum weight matching} problems can be solved in time $\tilde{O}(m\sqrt{n})$, a bound that has resisted improvement despite decades of research.

• (Here $m$ and $n$ are the number of edges and vertices.) In this article we demonstrate that this "$m\sqrt{n}$ barrier" is extremely fragile, in the following sense.
• For any $\epsilon>0$, we give an algorithm that computes a $(1-\epsilon)$-approximate maximum weight matching in $O(m\epsilon^{-1}\log\epsilon^{-1})$ time, that is, optimal {\em linear time} for any fixed $\epsilon$.
• Our algorithm is dramatically simpler than the best exact maximum weight matching algorithms on general graphs and should be appealing in all applications that can tolerate a negligible relative error.