Competitive Analysis for Multi-Commodity Ski-Rental Problem
Binghan Wu, Wei Bao, Dong Yuan, Bing Zhou
Abstract
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.
BibTeX
@inproceedings{ijcai2022p648,
title = {Competitive Analysis for Multi-Commodity Ski-Rental Problem},
author = {Wu, Binghan and Bao, Wei and Yuan, Dong and Zhou, Bing},
booktitle = {Proceedings of the Thirty-First International Joint Conference on
Artificial Intelligence, {IJCAI-22}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Lud De Raedt},
pages = {4672--4678},
year = {2022},
month = {7},
note = {Main Track},
doi = {10.24963/ijcai.2022/648},
url = {https://doi.org/10.24963/ijcai.2022/648},
}