

















Abstract:Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.
| Comments: | To appear in ICML 2026 |
| Subjects: | Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.26886 [cs.DS] |
| (or arXiv:2605.26886v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2605.26886 arXiv-issued DOI via DataCite (pending registration) |
From: Yongho Shin [view email]
[v1]
Tue, 26 May 2026 11:47:58 UTC (252 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。