RAIRO-Theor. Inf. Appl.
Volume 51, Number 2, April-June 2017
|Page(s)||91 - 98|
|Published online||26 October 2017|
A Better bound of randomized algorithms for the multislope ski-rental problem∗
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.
Received: 11 April 2017
Accepted: 11 September 2017
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 .
Mathematics Subject Classification: 68W27 / 91A80
Key words: Online algorithms / ski rental / randomized algorithms / competitive ratio
© EDP Sciences 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.