Timezone: »
Oral
The Primal-Dual method for Learning Augmented Algorithms
Etienne Bamas · Andreas Maggiori · Ola Svensson
Thu Dec 10 06:15 PM -- 06:30 PM (PST) @ Orals & Spotlights: Optimization
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.
Author Information
Etienne Bamas (EPFL)
Andreas Maggiori (EPFL)
Ola Svensson (EPFL)
Related Events (a corresponding poster, oral, or spotlight)
-
2020 Poster: The Primal-Dual method for Learning Augmented Algorithms »
Fri. Dec 11th 05:00 -- 07:00 AM Room Poster Session 6 #1810
More from the Same Authors
-
2021 Poster: Nearly-Tight and Oblivious Algorithms for Explainable Clustering »
Buddhima Gamlath · Xinrui Jia · Adam Polak · Ola Svensson -
2021 Poster: Parallel and Efficient Hierarchical k-Median Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Ashkan Norouzi-Fard · Christian Sohler · Ola Svensson -
2020 Poster: Learning Augmented Energy Minimization via Speed Scaling »
Etienne Bamas · Andreas Maggiori · Lars Rohwedder · Ola Svensson -
2020 Poster: Fast and Accurate $k$-means++ via Rejection Sampling »
Vincent Cohen-Addad · Silvio Lattanzi · Ashkan Norouzi-Fard · Christian Sohler · Ola Svensson -
2020 Spotlight: Learning Augmented Energy Minimization via Speed Scaling »
Etienne Bamas · Andreas Maggiori · Lars Rohwedder · Ola Svensson -
2016 Poster: Linear Relaxations for Finding Diverse Elements in Metric Spaces »
Aditya Bhaskara · Mehrdad Ghadiri · Vahab Mirrokni · Ola Svensson