This paper studies online algorithms augmented with multiple machine-learned predictions. While online algorithms augmented with a single prediction have been extensively studied in recent years, the literature for the multiple predictions setting is sparse. In this paper, we give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the best predictor. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting. Our algorithm can also be robustified, i.e., the algorithm can be simultaneously made competitive against the best prediction and the performance of the best online algorithm (without prediction).
翻译:本文研究在线算法,并辅以多种机学预测。虽然近年来对在线算法进行了广泛研究,但多预测环境的文献很少。在本文中,我们为在线问题提供了一个通用算法框架,以涵盖多种预测,从而获得与最佳预测者的业绩相比具有竞争力的在线解决方案。我们的算法将预测纳入对在线算法的典型潜在分析中。我们运用我们的算法框架来解决传统问题,如在线套件覆盖、(加权)缓存和多个预测环境中的在线设施位置。我们的算法也可以被强化,即,可以同时使算法与最佳预测和最佳在线算法(没有预测)的绩效(没有预测)相比具有竞争力。