On randomized greedy matchings

We analyze a randomized greedy matching algorithm (RGA) aimed at producing a matching with a large number of edges in a given weighted graph. RGA was first introduced and studied by Dyer and Frieze in [3] for unweighted graphs. In the weighted version, at each step a new edge is chosen from the remaining graph with probability proportional to its weight, and is added to the matching. The two vertices of the chosen edge are removed, and the step is repeated until there are no edges in the remaining graph. We analyze the expected size μ( G ) of the number of edges in the output matching produced by RGA, when RGA is repeatedly applied to the same graph G . Let r ( G )=μ( G )/ m ( G ), where m ( G ) is the maximum number of edges in a matching in G . For a class of graphs, let ρ() be the infimum values r ( G ) over all graphs G in (i.e., ρ is the “worst” performance ratio of RGA restricted to the class ). Our main results are bound for μ, r , and ρ. For example, the following results improve or generalize similar results obtained in [3] for the unweighted version of RGA; \begin{eqnarray*}r(G)&\ge&{1\over 2‐|V|/2|E|}\quad \mbox{(if $G$ has a perfect matching)}\\ {\sqrt{26}‐4\over 2}&\le&\rho(\hbox{\sf SIMPLE PLANAR GRAPHS})\le.68436349\\ \rho(\hbox{SIMPLE $\Delta$‐GRAPHS})&\ge&{1\over2}+{\sqrt{(\Delta‐1)^2+1}‐(\Delta‐1)\over2}\end{eqnarray*} (where the class $\Delta$\hbox{\sf-GRAPHS}$ is the set of graphs of maximum degree at most Δ). © 1997 John Wiley & Sons, Inc.  Random Struct. Alg. , 10 : 353–383, 1997