# Semi-Online Bipartite Matching

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2018.

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

- [A Survey of Machine Learning for Computer Architecture and Systems](https://mlsanity.com/paper/2102.07952/) (2021)
- [Logarithmic Regret from Sublinear Hints](https://mlsanity.com/paper/2111.05257/) (2021)
- [(Optimal) Online Bipartite Matching with Degree Information](https://mlsanity.com/paper/2110.11439/) (2021)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Robustification of Online Graph Exploration Methods](https://mlsanity.com/paper/2112.05422/) (2021)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [Online Capacity Scaling Augmented With Unreliable Machine Learning Predictions](https://mlsanity.com/paper/2101.12160/) (2021)
- [Online Primal-Dual Algorithms with Predictions for Packing Problems](https://mlsanity.com/paper/2110.00391/) (2021)
- [Time Fairness in Online Knapsack Problems](https://mlsanity.com/paper/2305.13293/) (2023)
- [Sorting and Hypergraph Orientation under Uncertainty with Predictions](https://mlsanity.com/paper/2305.09245/) (2023)
- [Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems](https://mlsanity.com/paper/2402.08701/) (2024)
- [Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms](https://mlsanity.com/paper/2510.15076/) (2025)

## Abstract (arXiv)

In this paper we introduce the semi-online model that generalizes the classical online computational model. The semi-online model postulates that the unknown future has a predictable part and an adversarial part; these parts can be arbitrarily interleaved. An algorithm in this model operates as in the standard online model, i.e., makes an irrevocable decision at each step. We consider bipartite matching in the semi-online model, for both integral and fractional cases. Our main contributions are competitive algorithms for this problem that are close to or match a hardness bound. The competitive ratio of the algorithms nicely interpolates between the truly offline setting (no adversarial part) and the truly online setting (no predictable part).