2022-08-10T10:58:36Zhttps://soar-ir.repo.nii.ac.jp/oaioai:soar-ir.repo.nii.ac.jp:000195692021-10-12T00:43:32Z1221:1222Analysis of Lower Bounds for the Multislope Ski-Rental ProblemFujiwara, HiroshiKonno, YasuhiroFujito, ToshihirocopyrightÂ©2014 IEICEonline algorithmcompetitive analysisonline optimizationski-rental problemsThe 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.ArticleIEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES. E97A(6): 1200-1205 (2014)IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG2014engjournal articleVoRhttp://hdl.handle.net/10091/00020330https://soar-ir.repo.nii.ac.jp/records/19569https://doi.org/10.1587/transfun.E97.A.120010.1587/transfun.E97.A.12001745-1337IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCESE97A612001205https://soar-ir.repo.nii.ac.jp/record/19569/files/Analysis_of_Lower_Bounds_for_the_Multislope_Ski-Rental_Problem_fujiwara_konno_fujito.pdfapplication/pdf1.0 MB2018-03-09