Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
This work addresses online matching algorithms for researchers in theoretical computer science and operations research, but it is incremental as it builds upon prior methods by removing assumptions on matching size.
The paper tackles the online bipartite matching problem in the random arrival order model by generalizing a learning-augmented approach to handle cases where the optimal matching size is not necessarily n, achieving (1-o(1))-consistency and (β-o(1))-robustness with smooth degradation in competitive ratio as prediction error increases.
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 < α\le 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.