Improved distributed approximate matching
Zvi Lotker, Boaz Patt-Shamir, Seth Pettie · 2008
We present improved algorithms for finding approximately optimal matchings in both weighted and unweighted graphs. For unweighted graphs, we give an algorithm providing >(1-ε-approximation in O(log n) time for any constant ε > 0. This result improves on the classical 1 over 2-approximation due to Israeli and Itai. As a by-product, we also provide an improved algorithm for unweighted matchings in bipartite graphs. In the context of weighted graphs, we give another algorithm which provides (1 over 2-ε) approximation in general graphs in O(log n)time. The latter result improves on the known (1 over 4-ε-approximation in O(log n)time.