Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis

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). In this work, we explore the limitation of the primal-dual analysis of Ranking and aim to bridge the gap between unweighted and vertex-weighted graphs. We show that the competitive ratio of Ranking is between 0.686 and 0.703, under our current knowledge of Ranking and the framework of primal-dual analysis. This confirms a conjecture by Huang, Tang, Wu, and Zhang (TALG 2019), stating that the primal-dual analysis could lead to a competitive ratio that is very close to 0.696. Our analysis involves proper discretizations of a variational problem and uses LP solver to pin down the numerical number. As a bonus of our discretization approach, our competitive analysis of Ranking applies to a more relaxed random arrival model. E.g., we show that even when each online vertex arrives independently at an early or late stage, the Ranking algorithm is at least 0.665-competitive, beating the 1-1/e ≈ 0.632 competitive ratio under the adversarial arrival model.