Online algorithms with multiple predictions

K Anand, R Ge, A Kumar… - … Conference on Machine …, 2022 - proceedings.mlr.press
International Conference on Machine Learning, 2022proceedings.mlr.press
This paper studies online algorithms augmented with multiple machine-learned predictions.
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 solution obtained from the predictions. 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 …
Abstract
This paper studies online algorithms augmented with multiple machine-learned predictions. 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 solution obtained from the predictions. 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.
proceedings.mlr.press