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 . 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 proposed by Lotker et al. to .
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 = {http://archive.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 - http://archive.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 http://archive.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. http://archive.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 :