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

Bo Peng, Zhihao Gavin Tang

Abstract: 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 \approx 0.632$ competitive ratio under the adversarial arrival model.

Introduction

Online bipartite matching is a fundamental problem in algorithmic theory with significant practical applications in online advertising and resource allocation. In this setting, offline items are matched to online agents who arrive sequentially. The Ranking algorithm is the standard approach, known for its optimal $1-1/e \approx 0.632$ performance under adversarial arrivals. However, its performance under random arrival orders is significantly better, though proving tight bounds for vertex-weighted graphs has been analytically challenging.

Historically, while unweighted graphs reached a $0.696$ competitive ratio, vertex-weighted graphs lagged at $0.662$ due to limitations in the standard primal-dual analysis. This paper addresses this gap by exploring the fundamental limits of the primal-dual framework and providing a new, tighter lower bound.

Primal-Dual Framework and Discretization

The authors utilize a randomized primal-dual framework where dual variables represent the "prices" of offline items and "utilities" of online buyers. The goal is to find functions $\alpha(x)$ and $\beta(x)$ that characterize these dual values to lower-bound the algorithm's total weight.

The primal-dual framework analyzes matching scenarios based on arrival times and vertex ranks to bound algorithm performance.

To bypass the analytical barriers of continuous variational problems, the researchers introduced a discretization approach. By partitioning the arrival times and ranks into a grid, they transformed the optimization problem into a large-scale Linear Program (LP).

Discretizing the continuous problem into a grid allows for the use of numerical LP solvers to find tight competitive ratios.

This method allows for the use of high-performance solvers like Gurobi to numerically determine the competitive ratio. To handle the exponential number of constraints in the upper bound analysis, an iterative local search algorithm was developed to identify the most critical constraints.

Key Results

  • New Competitive Bounds: The study establishes that Ranking is at least 0.6862-competitive for vertex-weighted graphs, moving significantly closer to the $0.696$ benchmark. It also shows an upper bound of 0.7027 for the current primal-dual framework.
  • Independent Random Arrival (IRA) Model: The analysis extends to a more relaxed model where nodes arrive independently in stages. Even with only two stages ("early" and "late"), the algorithm achieves a 0.6656 ratio, demonstrating that full randomness is not required to outperform adversarial benchmarks.
  • Conjecture Confirmation: These results provide strong numerical evidence for the 2019 conjecture that primal-dual analysis can indeed reach the $0.696$ ratio observed in unweighted cases.

Limitations and Future Outlook

The current lower bound of $0.6862$ is constrained by computational limits; the authors solved LPs up to a grid size of $11 \times 12$. Increased computing power could potentially push this value even closer to $0.696$. While the results are numerical, they provide a roadmap for future analytical proofs and highlight the importance of minimal randomness in maintaining high algorithmic performance in dynamic environments.

Summary updated

Abstract

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 \approx 0.632$ competitive ratio under the adversarial arrival model.
BibTeX
@misc{peng2025revisiting,
  author = {Bo Peng and Zhihao Gavin Tang},
  title = {{Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis}},
  year = {2025},
  eprint = {2503.04196},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.04196},
}
Figure