Skip to yearly menu bar Skip to main content


Online Algorithms with Multiple Predictions

Keerti Anand · Rong Ge · Amit Kumar · Debmalya Panigrahi

Hall E #603

Keywords: [ T: Optimization ] [ T: Learning Theory ] [ OPT: Optimization and Learning under Uncertainty ] [ OPT: Discrete and Combinatorial Optimization ]


This paper studies online algorithms augmented with {\em 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 {\em 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.

Chat is not available.