Learning-augmented Online Algorithm for Two-level Ski-rental Problem
Keyuan Zhang Zhongdong Liu Nakjung Choi Bo Ji
In this paper, we study the two-level ski-rental problem,where a user needs
to fulfill a sequence of demands for multiple items by choosing one of the
three payment options: paying for the on-demand usage (i.e., rent), buying
individual items (i.e., single purchase), and buying all the items (i.e., combo
purchase). Without knowing future demands, the user aims to minimize the total
cost (i.e., the sum of the rental, single purchase, and combo purchase costs)
by balancing the trade-off between the expensive upfront costs (for purchase)
and the potential future expenses (for rent). We first design a robust online
algorithm (RDTSR) that offers a worst-case performance guarantee. While online
algorithms are robust against the worst-case scenarios, they are often overly
cautious and thus suffer a poor average performance in typical scenarios. On
the other hand, Machine Learning (ML) algorithms typically show promising
average performance in various applications but lack worst-case performance
guarantees. To harness the benefits of both methods, we develop a
learning-augmented algorithm (LADTSR) by integrating ML predictions into the
robust online algorithm, which outperforms the robust online algorithm under
accurate predictions while ensuring worst-case performance guarantees even when
predictions are inaccurate. Finally, we conduct numerical experiments on both
synthetic and real-world trace data to corroborate the effectiveness of our
approach.