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
Accepté le :
DOI : 10.1051/ita/2017009
Mots-clés : Online algorithms, ski rental, randomized algorithms, competitive ratio
@article{ITA_2017__51_2_91_0, author = {Hu, Maolin and Xu, Weijun}, title = {A {Better} bound of randomized algorithms for the multislope ski-rental problem}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {91--98}, publisher = {EDP-Sciences}, volume = {51}, number = {2}, year = {2017}, doi = {10.1051/ita/2017009}, mrnumber = {3731539}, zbl = {1383.68102}, language = {en}, url = {https://www.numdam.org/articles/10.1051/ita/2017009/} }
TY - JOUR AU - Hu, Maolin AU - Xu, Weijun TI - A Better bound of randomized algorithms for the multislope ski-rental problem JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2017 SP - 91 EP - 98 VL - 51 IS - 2 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ita/2017009/ DO - 10.1051/ita/2017009 LA - en ID - ITA_2017__51_2_91_0 ER -
%0 Journal Article %A Hu, Maolin %A Xu, Weijun %T A Better bound of randomized algorithms for the multislope ski-rental problem %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2017 %P 91-98 %V 51 %N 2 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ita/2017009/ %R 10.1051/ita/2017009 %G en %F ITA_2017__51_2_91_0
Hu, Maolin; Xu, Weijun. A Better bound of randomized algorithms for the multislope ski-rental problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 2, pp. 91-98. doi : 10.1051/ita/2017009. https://www.numdam.org/articles/10.1051/ita/2017009/
On capital investment. Algorithmica 25 (1999) 22–36. | DOI | Zbl
, , , , and ,Nearly optimal strategies for special cases of on-line capital investment. Theoret. Comput. Sci. 302 (2003) 35–44. | DOI | Zbl
,Competitive optimal online leasing. Algorithmica 25 (1999) 116–140. | DOI | Zbl
, and ,On the Bahncard problem. Theoret. Comput. Sci. 268 (2001) 161–174. | DOI | MR | Zbl
,Competitive randomized algorithms for nonuniform problems. Algorithmica 11 (1994) 542–571. | DOI | MR | Zbl
, , and ,Competitive snoopy caching. Algorithmica 3 (1988) 77–119. | DOI | MR | Zbl
, , and ,On-line algorithms versus off-line algorithms: How much is it worth to know the future? Proc. of the IFIP 12th World Computer Congress 1 (1992) 416–429.
,Ski rental with two general options. Inf. Process Lett. 108 (2008) 339–422. | DOI | MR | Zbl
, and ,Rent, lease or buy: Randomized algorithms for multislope ski rental. SIAM J. Discrete Math. 26 (2012) 718–736. | DOI | MR | Zbl
, and .Cité par Sources :