# Competitive ratio of the ski rental problem

Reading about the Ski Rental Problem in Wikipedia, I got confused on the "when" is the buying of the skis occur. I could think of 2 possible ways, but each of them would have a different competitive ratio for a deterministic (and non- deterministic) algorithms:

Let's say that renting costs 1 dollar a day and buying costs 10 dollars.

• Buy the skis on the day before, this means that you can decide to buy the skis and never use them even once: So if you decide on an algorithm that rents for 9 days and buys the skis on the 9th day, skiing for exactly 9 days (which is the worst-case input for that algorithm) would cost (9 + 10)/9 = 2.111...
• Buying the skis on the current day: So you wake up on the morning of day N, you know already you can ski - and then decide if you want to buy or rent. This changes the competitive ratio of the algorithm in the worst case (for the input: skiing for exactly 9 days) to be: (9+10) / 10 = 1.9

The second method was presented in the Wikipedia article as well as in Algorithm Design and Application by Michael T. Goodrich and Roberto Tamassia. However -it is never written explicitly when does the buying of the skis occur.

My question here is - Are these 2 problems completely different from each other? and the first one can never have a competitive ratio of 2 or less ?

• I don't understand why you buy skiis on day 9 if you won't use them? That's why I think your first algorithm is not competitive. As far as I know, the best deterministic algorithm for the ski-rental problem is 2-competitive and is as follows: rent until you realize that you should have bought, then buy. Here is a useful link Online algorithms – Ribz Jan 21 '18 at 3:30

I think the first approach can give an arbitrarily bad competitive ratio for any algorithm: if we ski $$0$$ days, the optimal would be to neither buy nor rent (pay $$0$$), while any algorithm either buys or rents the skis before the first day (pay something $$>0$$).