On Optimal Consistency-Robustness Trade-Off for Learning-Augmented
  Multi-Option Ski Rental
Yongho Shin Changyeol Lee Hyung-Chan An
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.