A Unified Framework for Analysis of Randomized Greedy Matching Algorithms

Randomized greedy algorithms form one of the simplest yet most effective approaches for computing approximate matchings in graphs. In this paper, we focus on the class of vertex-iterative (VI) randomized greedy matching algorithms, which process the vertices of a graph G = (V, E) in some order π and, for each vertex v, greedily match it to the first available neighbor (if any) according to a preference order σ(v). Various VI algorithms have been studied, each corresponding to a different distribution over π and σ(v).

We develop a unified framework for analyzing this family of algorithms and use it to obtain improved approximation ratios for Ranking and FRanking, the state-of-the-art VI randomized greedy algorithms for the random-order and adversarial-order settings, respectively. In Ranking, the decision order π is drawn uniformly at random and used as the common preference order for all vertices, whereas FRanking uses an adversarially chosen decision order π and a uniformly random preference order σ shared by all vertices. We obtain an approximation ratio of 0.560 for Ranking, improving on the previous best ratio of 0.5469 by Derakhshan, Roghani, Saneian, and Yu [SODA 2026]. For FRanking, we obtain a ratio of 0.539, improving on the 0.521 bound of Huang, Kang, Tang, Wu, Zhao, and Zhu [JACM 2020]. These results also imply state-of-the-art approximation ratios for oblivious matching and fully online matching problems on general graphs.

Our analysis framework also enables us to prove improved approximation ratios for graphs with no short odd cycles. Such graphs form an intermediate class between general graphs and bipartite graphs. In particular, we show that Ranking is at least 0.570-competitive for graphs that are both triangle-free and pentagon-free. For graphs whose shortest odd cycle has length at least 129, we prove that Ranking is at least 0.615-competitive.