Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis
Bo Peng, Zhihao Gavin Tang · 2025
We revisit the celebrated Ranking algorithm by Karp, Vazirani, and Vazirani (STOC 1990) for online bipartite matching under the random arrival model, that is shown to be 0.696-competitive for unweighted graphs by Mahdian and Yan (STOC 2011) and 0.662-competitive for vertex-weighted graphs by Jin and Williamson (WINE 2021).