# Online bipartite matching with imperfect advice

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 51 references that are in the map.
- First posted on arXiv 16 May 2024.

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (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)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model](https://mlsanity.com/paper/2206.11397/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [A Novel Prediction Setup for Online Speed-Scaling](https://mlsanity.com/paper/2112.03082/) (2021)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [A Universal Error Measure for Input Predictions Applied to Online Graph Problems](https://mlsanity.com/paper/2205.12850/) (2022)
- [(Optimal) Online Bipartite Matching with Degree Information](https://mlsanity.com/paper/2110.11439/) (2021)
- [Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach](https://mlsanity.com/paper/2109.10380/) (2021)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [An Experimental Study of Algorithms for Online Bipartite Matching](https://mlsanity.com/paper/1808.04863/) (2018)
- [Learning-Augmented Algorithms for Online TSP on the Line](https://mlsanity.com/paper/2206.00655/) (2022)
- [Online Stochastic Matching: New Algorithms and Bounds](https://mlsanity.com/paper/1606.06395/) (2016)
- [Using Predicted Weights for Ad Delivery](https://mlsanity.com/paper/2106.01079/) (2021)
- [Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees](https://mlsanity.com/paper/2306.00172/) (2023)

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

- [Learning-Augmented Online Bipartite Fractional Matching](https://mlsanity.com/paper/2505.19252/) (2025)
- [Learning multivariate Gaussians with imperfect advice](https://mlsanity.com/paper/2411.12700/) (2024)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model](https://mlsanity.com/paper/2511.23388/) (2025)
- [Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget](https://mlsanity.com/paper/2509.00135/) (2025)
- [Product distribution learning with imperfect advice](https://mlsanity.com/paper/2511.10366/) (2025)
- [Parsimonious Learning-Augmented Online Metric Matching](https://mlsanity.com/paper/2605.26886/) (2026)
- [A Switching Framework for Online Interval Scheduling with Predictions](https://mlsanity.com/paper/2511.16194/) (2025)
- [Online Algorithms with Unreliable Guidance](https://mlsanity.com/paper/2602.20706/) (2026)
- [Online Allocation with Unknown Shared Supply](https://mlsanity.com/paper/2605.07080/) (2026)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)
- [Robust and Learned Online Matching in Growing Trees](https://mlsanity.com/paper/2609.40077/) (2026)

## Abstract (arXiv)

We study the problem of online unweighted bipartite matching with n offline vertices and n online vertices where one wishes to be competitive against the optimal offline algorithm. While the classic RANKING algorithm of Karp et al. [1990] provably attains competitive ratio of 1-1/e > 1/2, we show that no learning-augmented method can be both 1-consistent and strictly better than 1/2-robust under the adversarial arrival model. Meanwhile, under the random arrival model, we show how one can utilize methods from distribution testing to design an algorithm that takes in external advice about the online vertices and provably achieves competitive ratio interpolating between any ratio attainable by advice-free methods and the optimal ratio of 1, depending on the advice quality.