mlsanityData to 14 Oct 2026

Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis

arXiv 2302.06832 ↗First posted 14 Feb 2023cs.DS cs.LGcited by 16

Not on the map. Why?

Abstract (arXiv)

In this paper, we present improved learning-augmented algorithms for the multi-option ski rental problem. Learning-augmented algorithms take ML predictions as an added part of the input and incorporates these predictions in solving the given problem. Due to their unique strength that combines the power of ML predictions with rigorous performance guarantees, they have been extensively studied in the context of online optimization problems. Even though ski rental problems are one of the canonical problems in the field of online optimization, only deterministic algorithms were previously known for multi-option ski rental, with or without learning augmentation. We present the first randomized learning-augmented algorithm for this problem, surpassing previous performance guarantees given by deterministic algorithms. Our learning-augmented algorithm is based on a new, provably best-possible randomized competitive algorithm for the problem. Our results are further complemented by lower bounds for deterministic and randomized algorithms, and computational experiments evaluating our algorithms' performance improvements.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 14 of its 32 references that are in the map. First posted on arXiv 14 Feb 2023.

Builds on

14 of 32 references.

References · 14

  1. 2018Competitive caching with machine learned advicecited by 195
  2. 2020Algorithms with Predictionscited by 153
  3. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 80
  4. 2020Online metric algorithms with untrusted predictionscited by 75
  5. 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
  6. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  7. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  8. 2019Online Computation with Untrusted Advicecited by 42
  9. 2020Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancingcited by 27
  10. 2021Online Graph Algorithms with Predictionscited by 25
  11. 2022Parsimonious Learning-Augmented Cachingcited by 19
  12. 2021Online Facility Location with Predictionscited by 14
2 more
  1. 2022A Regression Approach to Learning-Augmented Online Algorithmscited by 12
  2. 2014The Multi-shop Ski Rental Problemcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 4; 2026: 6.

16 papers.

Sort:

  1. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  2. 2024Learning-Augmented Priority Queuescited by 7
  3. 2024Learning-Augmented Algorithms for the Bahncard Problemcited by 7
  4. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  5. 2023On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rentalcited by 2
  6. 2026Ski Rental with Distributional Predictions of Unknown Qualitycited by 2
  7. 2024On Approximability of ℓ22 Min-Sum Clusteringcited by 1
  8. 2024Online Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Healthcited by 0
  9. 2025Decision-Theoretic Approaches for Improved Learning-Augmented Algorithmscited by 0
  10. 2025Transductive and Learning-Augmented Online Regressioncited by 0
  11. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimizationcited by 0
  12. 2026Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratiocited by 0
4 more
  1. 2026Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completioncited by 0
  2. 2026Robust and Consistent Ski Rental with Distributional Advicecited by 0
  3. 2026Online Allocation with Unknown Shared Supplycited by 0
  4. 2026Learning-Augmented Algorithms for Online Vertex Covercited by 0