Competitive Analysis for Multi-Commodity Ski-Rental Problem
Competitive Analysis for Multi-Commodity Ski-Rental Problem
Binghan Wu, Wei Bao, Dong Yuan, Bing Zhou
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 4672-4678.
https://doi.org/10.24963/ijcai.2022/648
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.
Keywords:
Planning and Scheduling: Planning under Uncertainty
Planning and Scheduling: Applications
Planning and Scheduling: Theoretical Foundations of Planning