# Online Stochastic Matching: New Algorithms and Bounds

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2016.

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

- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [(Optimal) Online Bipartite Matching with Degree Information](https://mlsanity.com/paper/2110.11439/) (2021)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [Near-Optimal Reviewer Splitting in Two-Phase Paper Reviewing and Conference Experiment Design](https://mlsanity.com/paper/2108.06371/) (2021)
- [Near-Optimal Dynamic Matching via Coarsening with Application to Heart Transplantation](https://mlsanity.com/paper/2602.04989/) (2026)
- [Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model](https://mlsanity.com/paper/2511.23388/) (2025)
- [Online Task Assignment Problems with Reusable Resources](https://mlsanity.com/paper/2203.07605/) (2022)

## Abstract (arXiv)

Online matching has received significant attention over the last 15 years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 - 1/e) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam to 0.705; and (b) the vertex-weighted case, where we improve the 0.7250 ratio of Jaillet and Lu to 0.7299. We also consider an extension of stochastic rewards, a variant where each edge has an independent probability of being present. For the setting of stochastic rewards with non-integral arrival rates, we present a simple optimal non-adaptive algorithm with a ratio of 1 - 1/e. For the special case where each edge is unweighted and has a uniform constant probability of being present, we improve upon 1 - 1/e by proposing a strengthened LP benchmark.