Name
Abstract | ||
|---|---|---|
The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options in addition to the pure rent and buy options. For the additive general model, Lotker, Patt-Shamir and Rawitz [in: SIAM J. Discr. Math. 26 (2012) 718-736] obtained a randomized algorithm with the competitive ratio bounded by e-r(k)/r(0) /e-1. However, obtaining a better bound on the competitive factor as a function of the slopes parameters remains an open problem in their paper. In this paper, we study randomized algorithm for the additive multislope ski rental problem, and extend the competitive ratio bound e-r(k)/r(0) /e-1 proposed by Lotker et al. to e/e-1+r(k)/r(0) |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1051/ita/2017009 | RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS |
Keywords | Field | DocType |
Online algorithms,ski rental,randomized algorithms,competitive ratio | Ski rental problem,Randomized algorithm,Online algorithm,Mathematical optimization,Combinatorics,Open problem,Algorithm,Mathematics,Competitive analysis,Bounded function | Journal |
Volume | Issue | ISSN |
51 | 2 | 0988-3754 |
Citations | PageRank | References |
3 | 0.40 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maolin Hu | 1 | 3 | 0.40 |
| Wei-Jun Xu | 2 | 154 | 14.56 |