# Online Matching with General Arrivals

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2019.

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

- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [Stochastic Matching Bandits with Rare Optimization Updates](https://mlsanity.com/paper/2509.04194/) (2025)
- [Stochastic Matching via Local Sparsification](https://mlsanity.com/paper/2605.14195/) (2026)

## Abstract (arXiv)

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of frac12 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following. 1. For edge arrivals, randomization does not help --- no randomized algorithm is better than frac12 competitive. 2. For general vertex arrivals, randomization helps --- there exists a randomized (frac12+Omega(1))-competitive online matching algorithm.