Abstract | ||
---|---|---|
We introduce the continuously compounded interest rate into a generalized ski-rental problem with two options: either pay some rental proportionally to the usage time (the rent option), or buy the equipment and then pay some reduced rental proportionally to the usage time (the generalized buy option). Under the framework of competitive analysis, a randomized algorithm for the modified model is constructed and then is proved optimal by Yao@?s Lemma, and thus the optimal competitive ratio is obtained. The result shows that the introduction of the interest rate puts off the optimal purchase date and diminishes the uncertainty involved in the decision making. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.ipl.2012.04.006 | Inf. Process. Lett. |
Keywords | Field | DocType |
optimal randomized algorithm,optimal purchase date,rental proportionally,rent option,generalized buy option,reduced rental proportionally,generalized ski-rental problem,competitive analysis,usage time,interest rate,optimal competitive ratio,randomized algorithms | Ski rental problem,Discrete mathematics,Randomized algorithm,Mathematical optimization,Interest rate,Lemma (mathematics),Mathematics,Renting,Competitive analysis | Journal |
Volume | Issue | ISSN |
112 | 13 | 0020-0190 |
Citations | PageRank | References |
7 | 0.55 | 6 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xingyu Yang | 1 | 15 | 4.47 |
Wei-Guo Zhang | 2 | 557 | 39.22 |
Yong Zhang | 3 | 19 | 2.96 |
Wei-Jun Xu | 4 | 154 | 14.56 |