用预测提升在线匹配效率，误差大时仍能保底性能。
Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
- 基于预测的在线匹配算法，动态选择跟预测或保守策略。
- 在预测匹配至少占αn时，逼近最优匹配（1−o(1)一致性）。
- 适合有可信预测但怕出错的实时匹配场景。
研究随机到达顺序模型下的无权二分图在线匹配问题，包含n个离线顶点和n个在线顶点，在学习增强设置下，算法可获得在线顶点类型（邻域）的不可靠预测。我们扩展了Choo等（ICML 2024）的工作，不再假设最优匹配大小为n，仅要求预测匹配大小至少为αn（0 < α ≤ 1）。所提算法实现(1−o(1))的一致性与(β−o(1))的鲁棒性。同时证明，随着预测误差增大，竞争比在一致性和鲁棒性之间平滑下降。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。