# Learning-Augmented Online Bipartite Fractional Matching

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 25 May 2025.

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model](https://mlsanity.com/paper/2206.11397/) (2022)
- [Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources](https://mlsanity.com/paper/1711.08345/) (2017)
- [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)
- [An Experimental Study of Algorithms for Online Bipartite Matching](https://mlsanity.com/paper/1808.04863/) (2018)
- [Edge-Weighted Online Bipartite Matching](https://mlsanity.com/paper/2005.01929/) (2020)
- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Online Ad Allocation with Predictions](https://mlsanity.com/paper/2302.01827/) (2023)
- [Online Contention Resolution Schemes](https://mlsanity.com/paper/1508.00142/) (2015)
- [Class Fairness in Online Matching](https://mlsanity.com/paper/2203.03751/) (2022)
- [Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model](https://mlsanity.com/paper/1810.07903/) (2018)
- [Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing](https://mlsanity.com/paper/2210.11648/) (2022)
- [Fully Online Matching II: Beating Ranking and Water-filling](https://mlsanity.com/paper/2005.06311/) (2020)
- [Online Dependent Rounding Schemes for Bipartite Matchings, with Applications](https://mlsanity.com/paper/2301.08680/) (2023)
- [Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)](https://mlsanity.com/paper/2106.04863/) (2021)

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

- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (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)
- [Online Allocation with Unknown Shared Supply](https://mlsanity.com/paper/2605.07080/) (2026)
- [Learning-Augmented Algorithms for Online Vertex Cover](https://mlsanity.com/paper/2606.22831/) (2026)
- [Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays](https://mlsanity.com/paper/2607.27807/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

Online bipartite matching is a fundamental problem in online optimization, extensively studied both in its integral and fractional forms due to its theoretical significance and practical applications, such as online advertising and resource allocation. Motivated by recent progress in learning-augmented algorithms, we study online bipartite fractional matching when the algorithm is given advice in the form of a suggested matching in each iteration. We develop algorithms for both the vertex-weighted and unweighted variants that provably dominate the naive "coin flip" strategy of randomly choosing between the advice-following and advice-free algorithms. Moreover, our algorithm for the vertex-weighted setting extends to the AdWords problem under the small bids assumption, yielding a significant improvement over the seminal work of Mahdian, Nazerzadeh, and Saberi (EC 2007, TALG 2012). Complementing our positive results, we establish a hardness bound on the robustness-consistency tradeoff that is attainable by any algorithm. We empirically validate our algorithms through experiments on synthetic and real-world data.