LOWER BOUNDS FOR THE MULTISLOPE SKI-RENTAL PROBLEM
The multislope ski-rental problem is an extension of the classical ski-rental problem,where the player has several options of paying both of a per-time fee and an initial fee,in addition to pure renting and buying options.Damaschke gave a lower bound of 3.62 on the competitive ratio for the case where arbitrary number of options can be offered.In this paper we propose a scheme that for the number of options given as an input,provides a lower bound on the competitive ratio,by extending the method of Damaschke.This is the first to establish a lower bound for each of the 5- or-more-option cases,for example,a lower bound of 2.95 for the 5-option case,3.08 for the 6-option case,and 3.18 for the 7-option case.Moreover,it turns out that our lower bounds for the 3- and 4-option cases respectively coincide with the known upper bounds.We therefore conjecture that our scheme in general derives a matching lower and upper bound.
online algorithm competitive analysis online optimization ski-rental problems
Hiroshi Fujiwara Yasuhiro Konno Toshihiro Fujito
Toyohashi University of Technology, 1-1 Tenpaku-cho, Toyohashi, 441-8580 Japan
国际会议
11th International Symposium on Operations Research and its Applications(第11届运筹学及其应用国际研讨会)
安徽黄山
英文
23-28
2013-08-23（万方平台首次上网日期，不代表论文的发表时间）