Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428166 | Information Processing Letters | 2008 | 4 Pages |
Abstract
We define and solve a simple extension of the ski-rental problem [A.R. Karlin, M.S. Manasse, L. Rudolph, D.D. Sleator, Competitive snoopy caching, Algorithmica 3 (1) (1988) 77–119]. In the classical version, the algorithm needs to decide when to switch from renting to buying. In our version, no pure buy option is available: even after switching to the buy option, the algorithm needs to pay some reduced rent.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics