# Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 28 references that are in the map.
- First posted on arXiv 28 Nov 2025.

## Builds on (most cited first, 14 of 14)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Customizing ML Predictions for Online Algorithms](https://mlsanity.com/paper/2205.08715/) (2022)
- [Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model](https://mlsanity.com/paper/2206.11397/) (2022)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [An Experimental Study of Algorithms for Online Bipartite Matching](https://mlsanity.com/paper/1808.04863/) (2018)
- [Online Stochastic Matching: New Algorithms and Bounds](https://mlsanity.com/paper/1606.06395/) (2016)
- [Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees](https://mlsanity.com/paper/2306.00172/) (2023)

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

- [Learning-Augmented Algorithms for Online Vertex Cover](https://mlsanity.com/paper/2606.22831/) (2026)
- [Robust and Learned Online Matching in Growing Trees](https://mlsanity.com/paper/2609.40077/) (2026)

## Abstract (arXiv)

We study the online unweighted bipartite matching problem in the random arrival order model, with n offline and n online vertices, in the learning-augmented setting: The algorithm is provided with untrusted predictions of the types (neighborhoods) of the online vertices. We build upon the work of Choo et al. (ICML 2024, pp. 8762-8781) who proposed an approach that uses a prefix of the arrival sequence as a sample to determine whether the predictions are close to the true arrival sequence and then either follows the predictions or uses a known baseline algorithm that ignores the predictions and is β-competitive. Their analysis is limited to the case that the optimal matching has size n, i.e., every online vertex can be matched. We generalize their approach and analysis by removing any assumptions on the size of the optimal matching while only requiring that the size of the predicted matching is at least α n for any constant 0 < α ≤ 1. Our learning-augmented algorithm achieves (1-o(1))-consistency and (β-o(1))-robustness. Additionally, we show that the competitive ratio degrades smoothly between consistency and robustness with increasing prediction error.