Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs

The problem of computing a matching of maximum weight in a given edge-weighted graph is not known to be P-hard or in RNC. This paper presents four parallel approximation algorithms for this problem. The first is an RNC-approximation scheme, i.e., an RNC algorithm that computes a matching of weight at least 1 − ε times the maximum for any given constant ε > 0. The second one is an NC approximation algorithm achieving an approximation ratio of$$ \frac{1} {{2 + \varepsilon }} $$ for any fixed ε > 0. The third and fourth algorithms only need to know the total order of weights, so they are useful when the edge weights require a large amount of memories to represent. The third one is an NC approximation algorithm that finds a matching of weight at least $$ \frac{2} {{3\Delta + 2}} $$ times the maximum, where Δ is the maximum degree of the graph. The fourth one is an RNC algorithm that finds a matching of weight at least $$ \frac{1} {{2\Delta + 4}} $$ times the maximum on average, and runs in Ο(logΔ) time, not depending on the size of the graph.