The Primal-Dual method for Learning Augmented Algorithms
Etienne Bamas,Andreas Maggiori,Ola Svensson
The extension of classical online algorithms when provided with predictions isa new and active research area. In this paper, we extend the primal-dual methodfor online algorithms in order to incorporate predictions that advise the onlinealgorithm about the next action to take. We use this framework to obtain novelalgorithms for a variety of online covering problems. We compare our algorithmsto the cost of the true and predicted offline optimal solutions and show that thesealgorithms outperform any online algorithm when the prediction is accurate whilemaintaining good guarantees when the prediction is misleading.
