Randomized Greedy Matching on General Graphs

Randomized greedy algorithms are among the simplest and most effective methods for approximating maximum matchings, yet their performance on general graphs remains much less well understood than in the bipartite setting. In this talk, I will present recent progress on vertex-iterative randomized greedy matching algorithms for general graphs, focusing on Ranking and FRanking. I will describe new structural ideas and a unified analysis framework that yield improved approximation guarantees for these algorithms, including a 0.56 approximation ratio for Ranking and a 0.539 approximation ratio for FRanking. I will also discuss how the absence of short odd cycles leads to significantly stronger guarantees. More broadly, these results imply improved bounds for related models, including oblivious and fully online matching. The talk is based on joint work with Mohammad Roghani, Mohammad Saneian, and Tao Yu (SODA 2026), and on joint work with Tao Yu (STOC 2026).