Competitive Analysis for Two-Level Ski-Rental Problem
DOI:
https://doi.org/10.1609/aaai.v35i13.17429Keywords:
SchedulingAbstract
In this paper, we study a two-level ski-rental problem. There are multiple commodities, each one can be “rented” (paying for on-demand usage) or “purchased” (paying for life-time usage). There is also a combo purchase available so that all commodities can be purchased as a combo. Since the usages of the commodities in future are not known in advance, to minimize the overall cost, we design an online algorithm to decide if we rent a commodity, purchase a commodity, or make a combo purchase. We first propose a deterministic online algorithm. It can achieve 3 competitive ratio, which is optimal and tight. Next, we further propose a randomized online algorithm, leading to a e^σ/(e^σ-1) competitive ratio, where σ is the ratio between the price of a single commodity and the price of combo purchase. Finally, we apply simulation to verify the theoretical competitive ratios and evaluate the actual performance against benchmarks.Downloads
Published
2021-05-18
How to Cite
Wu, B., Bao, W., & Yuan, D. (2021). Competitive Analysis for Two-Level Ski-Rental Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 12034-12041. https://doi.org/10.1609/aaai.v35i13.17429
Issue
Section
AAAI Technical Track on Planning, Routing, and Scheduling