Competitive Analysis for Two-Level Ski-Rental Problem
| Autor: | Binghan Wu, Wei Bao, Dong Yuan |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Proceedings of the AAAI Conference on Artificial Intelligence. 35:12034-12041 |
| ISSN: | 2374-3468 2159-5399 |
| DOI: | 10.1609/aaai.v35i13.17429 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|