论文标题
学习增强算法的原始偶对偶的方法
The Primal-Dual method for Learning Augmented Algorithms
论文作者
论文摘要
在提供预测时，经典在线算法的扩展是一个新的活跃研究领域。在本文中，我们扩展了在线算法的原始偶对偶的方法，以结合有关在线算法的预测，以了解下一个动作。我们使用此框架来获取新的算法，以解决各种在线涵盖问题。我们将我们的算法与真实和预测的离线最佳解决方案的成本进行比较，并表明当预测准确时，在预测误导时保持良好的保证时，这些算法的表现优于任何在线算法。
The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms in order to incorporate predictions that advise the online algorithm about the next action to take. We use this framework to obtain novel algorithms for a variety of online covering problems. We compare our algorithms to the cost of the true and predicted offline optimal solutions and show that these algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.
