Towards a Better Understanding of Randomized Greedy Matching

There has been a long history for studying randomized greedy matching algorithms since the work by Dyer and Frieze~(RSA 1991). We follow this trend and consider the problem formulated in the oblivious setting, in which the algorithm makes (random) decisions that are essentially oblivious to the input graph. We revisit the textsfModified Randomized Greedy (MRG) algorithm by Aronson et al.~(RSA 1995) that is proved to be (0.5+ε)-approximate. In particular, we study a weaker version of the algorithm named textsfRandom Decision Order (RDO) that in each step, randomly picks an unmatched vertex and matches it to an arbitrary neighbor if exists. We prove the textsfRDO algorithm is 0.639-approximate and 0.531-approximate for bipartite graphs and general graphs respectively. As a corollary, we substantially improve the approximation ratio of textsfMRG. Furthermore, we generalize the textsfRDO algorithm to the edge-weighted case and prove that it achieves a 0.501 approximation ratio. This result solves the open question by Chan et al.~(SICOMP 2018) about the existence of an algorithm that beats greedy in this setting. As a corollary, it also solves the open questions by Gamlath et al.~(SODA 2019) in the stochastic setting.