2022-09-28T13:32:29Zhttps://soar-ir.repo.nii.ac.jp/oaioai:soar-ir.repo.nii.ac.jp:000195662021-10-12T00:43:25Z1221:1222On the best possible competitive ratio for the multislope ski-rental problemFujiwara, HiroshiKitano, TakumaFujito, ToshihiroThe original publication is available at www.springerlink.comOnline algorithmCompetitive analysisOnline optimizationSki-rental problemMathematical programmingThe multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options besides the pure rent and buy options. In this problem the hardness of an instance, which is the setting of options, significantly affects the player's performance. There is an algorithm that for a given instance, computes the best possible strategy. However, the output is given as numerical values and therefore the relational nature between an instance and the best possible performance for it has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than cannot be achieved. More precisely, a tight lower bound on the best possible performance is obtained in a closed form parametrized by the number of options. Furthermore, we establish a matching upper and lower bound on the competitive ratio each for the 3-option and 4-option problems.ArticleJOURNAL OF COMBINATORIAL OPTIMIZATION. 31(2): 463-490 (2016)SPRINGER2016engjournal articleAMhttp://hdl.handle.net/10091/00020327https://soar-ir.repo.nii.ac.jp/records/19566https://doi.org/10.1007/s10878-014-9762-910.1007/s10878-014-9762-91382-6905JOURNAL OF COMBINATORIAL OPTIMIZATION312463490https://soar-ir.repo.nii.ac.jp/record/19566/files/On_the_Best_Possible_Competitive_Ratio_for_the_Multislope_Ski-Rental_Problem.pdfapplication/pdf313.4 kB2018-03-09