The Primal-Dual method for Learning Augmented Algorithms
arXiv:2010.11632
Abstract
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.
30 pages, 11 figures. To appear in NeurIPS 2020 (oral)
References in corpus (7)
- Improving Online Algorithms via ML Predictions
- A Model for Learned Bloom Filters, and Optimizing by Sandwiching
- Revenue Optimization with Approximate Bid Predictions
- Scheduling with Predictions and the Price of Misprediction
- Learning Space Partitions for Nearest Neighbor Search
- Learning-Assisted Competitive Algorithms for Peak-Aware Energy Scheduling
- Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions