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:
E i = ∑ j P ( A L G j ) ⋅ A L G j ( i ) {\displaystyle E_{i}=\sum _{j}P(ALG_{j})\cdot ALG_{j}(i)} , where A L G j ( i ) {\displaystyle ALG_{j}(i)} is the competitive ratio for instance i, given A L G j {\displaystyle ALG_{j}} . Consequently, the competitive ratio of a randomized algorithm is given by the worst value of E i {\displaystyle 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 A L G h e a d s {\displaystyle ALG_{heads}} and A L G t a i l s {\displaystyle ALG_{tails}} , respectively. E i = P ( A L G h e a d s ) ⋅ A L G h e a d s ( i ) + P ( A L G t a i l s ) ⋅ A L G t a i l s ( i ) = 1 2 ⋅ 1 + 1 2 ⋅ 1 = 1 {\displaystyle E_{i}=P(ALG_{heads})\cdot ALG_{heads}(i)+P(ALG_{tails})\cdot ALG_{tails}(i)={\frac {1}{2}}\cdot 1+{\frac {1}{2}}\cdot 1=1} , for i < 8 {\displaystyle i<8} .
… excerpt ends here. Continue reading the full article.
