Poster
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.