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.

The problem

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. Ski rental is one example of this class of problem.

The break-even algorithm

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. 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.

The randomized algorithm

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: , where ALG_j(i) is the competitive ratio for instance i, given ALG_j. Consequently, the competitive ratio of a randomized algorithm is given by the worst value of E_i over all given instances. 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. We may call the branches ALG_{heads} and ALG_{tails}, respectively. , for i < 8. , , and , for i \geq 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. first presented this algorithm with distribution where buying skis costs $b and renting costs $1. Its expected cost is at most e/(e-1) \approx 1.58 times what one would pay if one had known the number of days one would go skiing. No randomized algorithm can do better.

Applications