On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental
Not on the map. Why?
Abstract (arXiv)
The learning-augmented multi-option ski rental problem generalizes the classical ski rental problem in two ways: the algorithm is provided with a prediction on the number of days we can ski, and the ski rental options now come with a variety of rental periods and prices to choose from, unlike the classical two-option setting. Subsequent to the initial study of the multi-option ski rental problem (without learning augmentation) due to Zhang, Poon, and Xu, significant progress has been made for this problem recently in particular. The problem is very well understood when we relinquish one of the two generalizations -- for the learning-augmented classical ski rental problem, algorithms giving best-possible trade-off between consistency and robustness exist; for the multi-option ski rental problem without learning augmentation, deterministic/randomized algorithms giving the best-possible competitiveness have been found. However, in presence of both generalizations, there remained a huge gap between the algorithmic and impossibility results. In fact, for randomized algorithms, we did not have any nontrivial lower bounds on the consistency-robustness trade-off before. This paper bridges this gap for both deterministic and randomized algorithms. For deterministic algorithms, we present a best-possible algorithm that completely matches the known lower bound. For randomized algorithms, we show the first nontrivial lower bound on the consistency-robustness trade-off, and also present an improved randomized algorithm. Our algorithm matches our lower bound on robustness within a factor of e/2 when the consistency is at most 1.086.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 31 of its 45 references that are in the map. First posted on arXiv 5 Dec 2023.
Builds on
31 of 45 references.
References · 31
- 2018Competitive caching with machine learned advicecited by 195
- 2017The Case for Learned Index Structurescited by 188
- 2020Algorithms with Predictionscited by 153
- 2020The Primal-Dual method for Learning Augmented Algorithmscited by 80
- 2020Online metric algorithms with untrusted predictionscited by 75
- 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
- 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
- 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
- 2021Faster Matchings via Learned Dualscited by 56
- 2019Scheduling with Predictions and the Price of Mispredictioncited by 47
- 2019Online Computation with Untrusted Advicecited by 42
- 2020Better and Simpler Learning-Augmented Online Cachingcited by 38
19 more
- 2020Learning Augmented Energy Minimization via Speed Scalingcited by 38
- 2020Online Algorithms for Weighted Paging with Predictionscited by 29
- 2021Flow Time Scheduling with Uncertain Processing Timecited by 29
- 2020Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancingcited by 27
- 2021Online Graph Algorithms with Predictionscited by 25
- 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
- 2022Customizing ML Predictions for Online Algorithmscited by 21
- 2022Parsimonious Learning-Augmented Cachingcited by 19
- 2022Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Modelcited by 19
- 2022Chasing Convex Bodies and Functions with Black-Box Advicecited by 19
- 2020Learning-Augmented Weighted Pagingcited by 17
- 2023Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysiscited by 16
- 2021Online Facility Location with Predictionscited by 14
- 2022A Regression Approach to Learning-Augmented Online Algorithmscited by 12
- 2021Double Coverage with Machine-Learned Advicecited by 10
- 2021Using Predicted Weights for Ad Deliverycited by 7
- 2022Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertaintycited by 7
- 2021Learning-Augmented Algorithms for Online Steiner Treecited by 6
- 2014The Multi-shop Ski Rental Problemcited by 4
Built on by
Citing papers per year: 2026: 2.
2 papers.