From Mining of Massive datasets

! Exercise 8.2.1: A popular example of the design of an on-line algorithm to

minimize the competitive ratio is the ski-buying problem.3 Suppose you can buy

skis for $100, or you can rent skis for $10 per day. You decide to take up skiing,

but you dont know if you will like it. You may try skiing for any number of

days and then give it up. The merit of an algorithm is the cost per day of skis,

and we must try to minimize this cost.

One on-line algorithm for making the rent/buy decision is buy skis immediately.

If you try skiing once, fall down and give it up, then this on-line

algorithm costs you $100 per day, while the optimum off-line algorithm would

have you rent skis for $10 for the one day you used them. Thus, the competitive

ratio of the algorithm buy skis immediately is at most 1/10th, and that is

in fact the exact competitive ratio, since using the skis one day is the worst

possible outcome for this algorithm. On the other hand, the on-line algorithm

always rent skis has an arbitrarily small competitive ratio. If you turn out to

really like skiing and go regularly, then after n days, you will have paid $10n or

$10/day, while the optimum off-line algorithm would have bought skis at once,

and paid only $100, or $100/n per day.

Your question: design an on-line algorithm for the ski-buying problem that

has the best possible competitive ratio. What is that competitive ratio? Hint:

Since you could, at any time, have a fall and decide to give up skiing, the only

thing the on-line algorithm can use in making its decision is how many times

previously you have gone skiing.