# The Multi-shop Ski Rental Problem

arXiv: https://arxiv.org/abs/1404.2671 · HTML: https://mlsanity.com/paper/1404.2671/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Apr 2014.

## Built on by (most cited first, 4 of 4)

- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [A Regression Approach to Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2205.08717/) (2022)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Competitive Algorithms for Multi-Agent Ski-Rental Problems](https://mlsanity.com/paper/2507.15727/) (2025)

## Abstract (arXiv)

We consider the em multi-shop ski rental problem. This problem generalizes the classic ski rental problem to a multi-shop setting, in which each shop has different prices for renting and purchasing a pair of skis, and a consumer has to make decisions on when and where to buy. We are interested in the em optimal online (competitive-ratio minimizing) mixed strategy from the consumer's perspective. For our problem in its basic form, we obtain exciting closed-form solutions and a linear time algorithm for computing them. We further demonstrate the generality of our approach by investigating three extensions of our basic problem, namely ones that consider costs incurred by entering a shop or switching to another shop. Our solutions to these problems suggest that the consumer must assign positive probability in exactly one shop at any buying time. Our results apply to many real-world applications, ranging from cost management in textttIaaS cloud to scheduling in distributed computing.