Improved ski rental strategies with partial timing signals achieve better cost ratios
Ski Rental with Uniform Stochastic Signals
Data Structures and Algorithms
Summary
The ski rental problem asks when it's best to keep renting or buy an item without knowing how long it will be used. The authors study a version where the algorithm receives a random timing signal that hints when the use might end. By focusing on signals that arrive uniformly at random, they find better strategies that reduce the cost compared to classic approaches. Surprisingly, even simple deterministic methods work nearly as well as the best possible ones in this setting.
What this means in practice
- •For cloud service operators: Optimize rental vs purchase decisions for cloud resources using partial timing signals to reduce operational costs.
- •For inventory managers: Improve purchase timing policies when demand duration clues are available as partial random signals to lower overstock costs.
A theory result. No direct application yet.
Authors
Tudor Cardas, Lucas Perotin, Bertrand Simon
Abstract
Ski rental is one of the most fundamental online problems, where an agent repeatedly decides whether it should continue renting for a service, or buy it at a one-time fixed cost. In classic online analysis, an adversary may freely select any arbitrary time horizon $t$ after which the instance terminates, hence leading to strong competitive ratio lower bounds of 2 (deterministic) and $e/(e-1)$ (randomized). We consider a novel but natural model aiming at limiting the adversary's power without degrading its flexibility. A stochastic signal, containing no information apart from its arrival time, is transmitted to the algorithm at a time drawn from a known distribution scaled to $[0,t]$. This framework allows us to account for visible effects of the adversary's choice to the algorithm. Focusing as a first step on uniform distributions, we show that the best possible competitive ratios are approximately $1.478$ (deterministic) and $1.438$ (randomized). Surprisingly, simplistic deterministic strategies already achieve a performance of $1.489$.