This is the optimal c-competitive solution to the Ski Rental Problem, with some explanation. Yup, it's a spoiler, but there are plenty of other online algorithm problems you can have a go at.


First off, what would the "omniscient" offline algorithm do? Obviously, it knows the total number of days you'll be skiing, and that's all that matters. If you'll be skiing 15 days or more, you should buy the skis (since renting will cost more than 15 x $10). If less, renting is your best choice.

But our online algorithm won't know the total number of days ahead of time. On the other hand, the input is rather limited: at day i, so long as you haven't bought the skis, the input is simply "it's day i, and we're still skiing". Once you buy the skis, there are no more decisions to make. So an online algorithm is really just a number N: if and when you reach day N, the algorithm says you should buy those skis. The input, in this reformulation, is simply D, the number of days you end up skiing.

So what N is best? If N is very low, you risk paying N x $10 + $150, when for a potentially short holiday you could have kept renting (and paid, say (N+1) x $10). If N is very high, you risk paying the cost of buying the skis many times over.

Unsurprisingly, perhaps, the answer is a half-way compromise: rent until day 15, then buy. This algorithm is 2-competitive. You never pay more than $300, so any other (offline) solution which involves buying the skis can be no more than twice as good. If the holiday ends any time up to day 15, renting is obviously optimal, and if it ends after day 15, even the optimal solution must involve paying at least $150. Thus, any "omniscient" algorithm can fare no better than paying half what our online algorithm does.

Is 2 optimal? Yes! Simply go through the considerations of the previous paragraph with N less than 15, and again with N greater than 15, and note that some value of D always makes you pay more than twice what you could have managed (with hindsight). "Balance" is often a good approach to online algorithms; it is often c-competitive for some intuitive c, and occasionally (as in this case) optimal.

Happy skiing!

Log in or register to write something here or to contact authors.