Geodesic
A Better bound of randomized algorithms for the multislope ski-rental problem
Hu, Maolin1 ; Xu, Weijun2
1 School of Mathematical Science, Huaiyin Normal University, Huaian, Jiangsu 223300, P.R. China.
2 School of Business Administration, South China University of Technology, Guangzhou 510641, P.R. China.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 2, pp. 91-98

Voir la notice de l'article provenant de la source Numdam

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 .

Reçu le :
Accepté le :
DOI : 10.1051/ita/2017009
Classification : 68W27, 91A80
Keywords: Online algorithms, ski rental, randomized algorithms, competitive ratio

Hu, Maolin 1 ; Xu, Weijun 2

1 School of Mathematical Science, Huaiyin Normal University, Huaian, Jiangsu 223300, P.R. China.
2 School of Business Administration, South China University of Technology, Guangzhou 510641, P.R. China. 
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :