The Primal-Dual method for Learning Augmented Algorithms
This work addresses the challenge of improving online algorithm performance for researchers and practitioners in optimization, though it is incremental as it builds on existing primal-dual frameworks.
The paper tackles the problem of enhancing online algorithms with predictions by extending the primal-dual method to incorporate advice on next actions, resulting in novel algorithms for online covering problems that outperform standard online algorithms when predictions are accurate and maintain robustness when predictions are misleading.
The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms in order to incorporate predictions that advise the online algorithm about the next action to take. We use this framework to obtain novel algorithms for a variety of online covering problems. We compare our algorithms to the cost of the true and predicted offline optimal solutions and show that these algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.