2
$\begingroup$

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 ?

$\endgroup$
  • $\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
0
$\begingroup$

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$).

So the problems are different, and for the first problem we cannot have a "good" algorithm.

New contributor
elrond is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.