Improved Approximation for Ranking on General Graphs
Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu · Society for Industrial and Applied Mathematics eBooks · 2026
In this paper, we study Ranking, a well-known randomized greedy matching algorithm, for general graphs. The algorithm was originally introduced by Karp, Vazirani, and Vazirani [STOC 1990] for the online bipartite matching problem with one-sided vertex arrivals, where it achieves a tight approximation ratio of \(1 -1/e\). It was later extended to bipartite graphs with random vertex arrivals by Mahdian and Yan [STOC 2011] and to general graphs by Goel and Tripathi [FOCS 2012]. The Ranking algorithm for general graphs is as follows: a permutation \(\sigma\) over the vertices is chosen uniformly at random. The vertices are then processed sequentially according to this order, with each vertex being matched to the first available neighbor (if any) according to the same permutation \(\sigma\).