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.
Introduction
The classical ski-rental problem is a fundamental dilemma in online algorithm theory: should a user rent equipment for a recurring fee or buy it for a one-time cost without knowing the total duration of use? While the optimal deterministic strategy for a single item is well-established—rent until cumulative fees equal the purchase price to guarantee a competitive ratio of 2—real-world applications often involve multiple interdependent commodities.
For instance, a cloud-based application requires a suite of services such as virtual machines, storage, and messaging simultaneously. Treating these as independent "rent-vs-buy" decisions is sub-optimal. This paper identifies this gap and proposes a coordinated strategy to minimize total system cost by considering commodities as a collective set rather than isolated items.
The Multi-Object Break-Even (MOBE) Algorithm
To address the multi-commodity challenge, we introduce the Multi-Object Break-Even (MOBE) algorithm. Unlike the classical approach that uses a single break-even point, MOBE calculates $N$ distinct thresholds ($\theta_1, \theta_2, \dots, \theta_N$) for $N$ different commodities.
Key Technical Contributions:
- Threshold Solver: An efficient $O(N^2)$ algorithm that groups commodities by their rent-to-buy ratios and sorts them by purchase price. It utilizes a recursive formula and binary search to identify the optimal timing for each purchase.
- Staggered Purchasing: MOBE coordinates purchase decisions so that cheaper components may be bought early to mitigate rental costs, while more expensive items are rented longer until their usage justifies the investment. This balances risk across the entire set.
- Competitive Bounds: We prove that MOBE’s competitive ratio is bounded between $\frac{e}{e-1} \approx 1.582$ and $2$. As the number of items increases and their ratios become more homogeneous, the performance approaches the lower bound.
Experimental Evaluation
The algorithm was evaluated using two primary methods:
- Numerical Simulations: Synthetic data was used to verify theoretical bounds across various rent-to-buy ratios and commodity counts (up to 100 items).
- Trace-Driven Experiment: The authors used a real-world dataset of forest fires in India (2008–2011) from Kaggle. They simulated a fire-alarm web application that scales its AWS infrastructure—specifically Fargate instances and SageMaker notebooks—based on unpredictable fire activity. This provided a realistic testbed for the algorithm's cost-efficiency against benchmarks like Offline Optimal (OP), Classical Ski-Rental (SR), Always Rent (AP), and Always Buy (AR).
Results and Discussion
Experimental results confirm that MOBE consistently achieves lower accumulated costs than independent strategies. In the cloud infrastructure scenario (Fargate + SageMaker), MOBE (labeled 'MB' in figures) demonstrated superior cost-efficiency compared to the classical independent ski-rental approach.
Numerical simulations further verified the theoretical competitive bounds. In scenarios with 100 homogeneous items, MOBE achieved a competitive ratio of 1.587, significantly outperforming the classical independent approach's ratio of 1.99. As shown in the competitive ratio distribution, the experimental ratios remain well within the theoretical upper bound $R^*$.
Conclusion
The MOBE algorithm provides a computationally light and theoretically robust solution for the multi-commodity ski-rental problem. By jointly optimizing purchase decisions, it significantly reduces total costs compared to traditional independent approaches, particularly in environments with many similar components like cloud computing. Future work may explore randomized variants or models with fluctuating market prices to further enhance performance.
Summary updated