Linear-Time Approximation for Maximum Weight Matching

Abstract

The maximum cardinality and maximum weight matching problems can be solved in Õ ( m √ n ) time, 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 √ n barrier” can be bypassed by approximation. For any ε > 0, we give an algorithm that computes a (1 − ε )-approximate maximum weight matching in O ( mε −1 log ε −1 ) time, that is, optimal linear time for any fixed ε . 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.