Randomized greedy matching

Abstract: "We consider a randomized version of the usual greedy algorithm for finding a large matching in a graph. We assume that the next edge is randomly chosen from those remaining at any stage. We analyse the expected performance of this algorithm when the input graph is fixed. We show that there are graphs for which this Randomized Greedy Algorithm (RGA) usually only obtains a matching close in size to that guaranteed by worst-case analysis (i.e. half the size of the maximum). For some classes of sparse graphs (e.g. planar graphs and forests) we prove that randomization does produce an improvement over the worst-case, the ratios to maximum being at least 6/11 and 0.76┬╖┬╖┬╖ respectively."