Computer Science/Discrete Mathematics Seminar I

It is a long-standing problem to lower bound the performance of randomized greedy algorithms for maximum matching. Aronson, Dyer, Frieze and Suen in1995 studied the modified randomized greedy (MRG) algorithm and proved that it approximates the maximum matching within a factor of at least $\frac{1}{2}+1/400,000$. They use heavy combinatorial methods in their analysis. We introduce a new technique we call Contrast Analysis, and show a $\frac{1}{2} + 1/256$ performance lower bound for the MRG algorithm.

Joint work with Matthias Poloczek