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 ?

  • $\begingroup$ 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 $\endgroup$ – Ribz Jan 21 '18 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.