I am trying to solve the ski rental problem with a small twist but I cannot seem to fully understand the solution or how to get there.
Any help is much appreciated.
The problem is the ski rental problem and the twist is as follows:
The rental price cuts by half with each day that goes by
Assume rental price is 1.
One time buying cost (from first day): B
One time buying cost (at day J): B – 0.5J
Suggest an online algorithm for the problem (when J is unknown).
At day J the algorithm needs to decide whether to keep renting or finally buy the gear.
The algorithm needs to have the best competitive ratio possible.
Calculate the competitive ratio (it’s unnecessary to prove whether it’s optimal).
I expect the worst case scenario to be renting until day 2B where the gear becomes free of cost.
But something aint adding up since worst case scenario would still be renting at this situation.