We present deterministic distributed algorithms for computing approximate maximum cardinality matchings and approximate maximum weight matchings. Our algorithm for the unweighted case computes a matching whose size is at least (1−e) times the optimal in Δ O(1/e) + O(1/e2) · log* (n) rounds where n is the number of vertices in the graph and Δ is the maximum degree. Our algorithm for the edge-weighted case computes a matching whose weight is at least (1 − e) times the optimal in log(min{1/ωmin, n/e})O(1/e). (Δ O(1/e) + log*(n)) rounds for edge-weights in [wmin, 1].   The best previous algorithms for both the unweighted case and the weighted case are by Lotker, Patt-Shamir, and Pettie (SPAA 2008). For the unweighted case they give a randomized (1 − e)-approximation algorithm that runs in O((log(n))e3) rounds. For the weighted case they give a randomized (1/2 − e)-approximation algorithm that runs in O(log(e−1) · log(n)) rounds. Hence, our results improve on the previous ones when the parameters Δ, e and wmin are constants (where we reduce the number of runs from O(log(n)) to O(log*(n))), and more generally when Δ, 1/e and 1/wmin are sufficiently slowly increasing functions of n. Moreover, our algorithms are deterministic rather than randomized.
['Guy Even', 'Moti Medina', 'Dana Ron']
Distributed Maximum Matching in Bounded Degree Graphs