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

arXiv: https://arxiv.org/abs/2503.04196 · HTML: https://mlsanity.com/paper/2503.04196/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Mar 2025.

## Built on by (most cited first, 1 of 1)

- [Stochastic Matching via Local Sparsification](https://mlsanity.com/paper/2605.14195/) (2026)

## Abstract (arXiv)

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.