Online Algorithms with Multiple Predictions
This work addresses the challenge of enhancing online algorithms with multiple predictions, which is an incremental advancement over single-prediction methods, benefiting areas like resource allocation and optimization.
The paper tackles the problem of designing online algorithms that can leverage multiple machine-learned predictions to improve performance, presenting a generic framework for online covering problems that achieves competitiveness against the best predictor, with applications to set cover, caching, and facility location.
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).