Ski Rental Problem
See: Online Task, Discrete Task.
References
2013
- http://en.wikipedia.org/wiki/Ski_rental_problem
- The ski rental problem is the name given to a class of problems in which there is a choice between continuing to pay a repeating cost or paying a one-time cost which eliminates or reduces the repeating cost.
- http://en.wikipedia.org/wiki/Ski_rental_problem#The_problem
- Many online problems have a sub-problem called the rent/buy problem. We need to decide whether to stay in the current state and pay a certain amount of cost per time unit, or switch to another state and pay some fixed large cost with no further payment.[1] Ski rental [2][3] is one classical toy example, where the rent/buy is the entire problem. Its basic version is as follows:
You are going skiing for an unknown number of days (you do not know the exact number due to various reasons, e.g., loss of interest, accidents that break your legs, or extremely bad weather). Assume that renting skis costs $1 per day and buying skis costs $10. Every day you have to decide whether to continue renting skis for one more day or buy a pair of skis. If you know in advance how many days you will go skiing, you can decide your minimum cost. For example, if you will be skiing for more than 10 days it will be cheaper to buy skis, while if you will be skiing for fewer than 10 days it will be cheaper to rent. (If you will ski for exactly 10 days you are indifferent.) The question is what to do when you do not know in advance how many days you will ski.
Formally, the problem can be set up as follows. There is a number of days d (unknown to you) that you will ski. We are looking for an algorithm that minimizes the ratio between what you pay using the algorithm (that does not know d) and what you would pay optimally if you knew d in advance. The problem is generally analyzed in the worst case, where the algorithm is fixed and then we look at the worst-case performance of the algorithm over all possible d. In particular, no assumptions are made regarding the distribution of d (and it is easy to see that, with knowledge of the distribution of d, a different analysis as well as different solutions would be preferred).
- Many online problems have a sub-problem called the rent/buy problem. We need to decide whether to stay in the current state and pay a certain amount of cost per time unit, or switch to another state and pay some fixed large cost with no further payment.[1] Ski rental [2][3] is one classical toy example, where the rent/buy is the entire problem. Its basic version is as follows:
- ↑ Steven S. Seiden. A guessing game and randomized online algorithms. Annual ACM Symposium on Theory of Computing, 2000. http://portal.acm.org/citation.cfm?id=335385
- ↑ A. R. Karlin, M. S. Manasse, L. A. McGeoch, and S. Owicki. Competitive randomized algorithms for non-uniform problems. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 22–24 January 1990, pp. 301-309. Also in Algorithmica, 11(6): 542-571, 1994. http://theory.lcs.mit.edu/classes/6.895/fall03/handouts/papers/karlin.pdf
- ↑ Claire Mathieu. Brown University. Lecture note: http://www.cs.brown.edu/~claire/Talks/skirental.pdf