Advertisement
Published in:
2011 | OriginalPaper | Chapter
On the Best Possible Competitive Ratio for Multislope Ski Rental
Authors : Hiroshi Fujiwara, Takuma Kitano, Toshihiro Fujito
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The multislope ski-rental problem [11] is an extension of the classical ski-rental problem [10], where the player has several
lease
options in addition to the pure
rent
and
buy
options. In this problem an
instance
, which is the setting of the options, significantly affects the player’s performance. There is an algorithm that for a given instance, computes the best possible strategy [1]. However, the output is given in numerical values and the relational nature between the instance and the best possible performance has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than
e
/(
e
− 1) ≈ 1.58 cannot be achieved. More precisely, according to the number of options, tight bounds are obtained in a closed form. Furthermore, we establish a matching upper and lower bound of the competitive ratio each for the 3-slope and 4-slope problems.