ON RANDOMIZED GREEDY MATCHINGS

We analyze a randomized greedy matching algorithm (RGA) aimed at produ cing 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 u nweighted graphs. In the weighted version, at each step a new edge is chosen from the remaining graph with probability proportional to its w eight, and is added to the matching. The two vertices of the chosen ed ge are removed, and the step is repeated until there are no edges in t he remaining graph. We analyze the expected size mu(G) of the number o f edges in the output matching produced by RGA, when RGA is repeatedly applied to the same graph G. Let r(G)= mu(G)/m(G), where m(G) is the maximum number of edges in a matching in G. For a class g of graphs, l et rho(g) be the infimum of the values r(G) over all graphs G in g (i. e., rho is the ''worst'' performance ratio of RGA restricted to the cl ass g). Our main results are bounds for mu, r, and rho. For example, t he following results improve or generalize similar results obtained in [3] for the unweighted version of RGA; r(G) greater than or equal to 1/2 - \v\/2\E\ (if G has a perfect matching), root 26 - 4/2 less than or equal to rho(SIMPLE PLANAR GRAPHS) less than or equal to .68436349, rho(SIMPLE Delta-GRAPHS) greater than or equal to 1/2 + root(Delta - 1)(2) + 1 - (Delta - 1)/2 (where the class Delta-GRAPHS is the set of graphs of maximum degree at most Delta). (C) 1997 John Wiley & Sons, I nc.