| Autor: |
Binghan Wu, Wei Bao, Dong Yuan, Bing Zhou |
| Rok vydání: |
2022 |
| Zdroj: |
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. |
| Popis: |
We investigate an extended version of the classical ski-rental problem with multiple commodities. A customer uses a set of commodities altogether, and he/she needs to choose payment options to cover the usage of each commodity without the knowledge of the future. The payment options of each commodity include (1) renting: to pay for an on-demand usage and (2) buying: to pay for the lifetime usage. It is a novel extension of the classical ski-rental problem which deals with only one commodity. To address this problem, we propose a new online algorithm called the Multi-Object Break-Even (MOBE) algorithm and conduct competitive analysis. We show that the tight lower and upper bounds of MOBE algorithm's competitive ratio are e/e-1 and 2 respectively against adaptive adversary under arbitrary renting and buying prices. We further prove that MOBE algorithm is an optimal online algorithm if commodities have the same rent-to-buy ratio. Numerical results verify our theoretical conclusion and demonstrate the advantages of MOBE in a real-world scenario. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
