用少量预测实现更优在线度量匹配，兼顾效率与性能。
Parsimonious Learning-Augmented Online Metric Matching
- 通过虚拟预测补全缺失信息，维持中间匹配质量。
- 理论证明在少预测下仍能保持良好性能边界。
- 适合资源受限场景下的在线匹配任务。
学习增强算法近年来在在线优化领域受到广泛关注，尤其关注预测数量与性能保障之间的权衡。本文将这一研究扩展至在线度量匹配问题，提出简洁的学习增强算法，并建立其性能的下界。方法上，将跟随预测框架拓展至稀疏预测场景，当无实际预测时，通过一个在线度量匹配算法生成虚拟预测，以维持执行过程中的良好中间匹配状态。此外，还进行了实证评估，验证了该方法的实际有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。