In computer science, the ski rental problem is a name given to a class of problems in which there is a choice between continuing to pay a repeating cost or paying a one-time cost which eliminates or reduces the repeating cost.
[1] Many online problems have a sub-problem called the rent-or-buy problem.
Given an expensive up front cost, or a less expensive repeating cost, with no knowledge of how the future will play out, at what point is it better to pay the up front cost to avoid a continued repeating cost?
Consider a person who decides to go skiing, but for an undecided number of days.
Renting skis costs $1 per day, whereas buying a pair of skis costs $10.
If the person knows in advance how many days they want to ski, then the breakeven point is 10 days.
Fewer than 10 days, renting is preferable, whereas with more than 10 days, buying is preferable.
However, with no advance knowledge of how long one will be skiing, the breakeven point is unclear.
A good algorithm will minimize the ratio of the cost when the number of days is known in advance to the cost when the number of days is not known in advance.
[2] Ski rental[3][4] is one example of this class of problem.
The break-even algorithm instructs one to rent for 9 days and buy skis on the morning of day 10 if one is still up for skiing.
[5] If one has to stop skiing during the first 9 days, it costs the same as what one would pay if one had known the number of days one would go skiing.
If one has to stop skiing after day 10, one's cost is $19 which is 90% more than what one would pay if one had known the number of days one would go skiing in advance.
This is the worst case for the break-even algorithm.
The break-even algorithm is known to be the best deterministic algorithm for this problem.
A person can flip a coin.
If it comes up heads, she buys skis on day eight; otherwise, she buys skis on day 10.
This is an instance of a randomized algorithm.
The expected cost is at most 80% more than what the person would pay if she had known the number of days she would go skiing, regardless of how many days she skis.
In particular, if the person skis for 10 days, her expected cost is 1/2 [7 +10] + 1/2 [9+10] = 18 dollars, only 80% excess instead of 90%.
A randomized algorithm can be understood as a composition of different algorithms, each one which occurs with a given probability.
We define the expected competitive ratio on a given instance i as:
is the competitive ratio for instance i, given
Consequently, the competitive ratio of a randomized algorithm is given by the worst value of
In the case of the coin flipping ski-rental, we note that the randomized algorithm has 2 possible branches: If the coin comes up heads, we buy on day 8, otherwise we buy on day 10.
Therefore, the competitive ratio of the randomized ski-rental coin flipping algorithm is 1.8.
The best randomized algorithm against an oblivious adversary is to choose some day i at random according to the following distribution p, rent for i-1 days and buy skis on the morning of day i if one are still up for skiing.
Karlin et al.[3] first presented this algorithm with distribution
where buying skis costs $
1.58 times what one would pay if one had known the number of days one would go skiing.