Bounds for the Multislope Ski-Rental Problem

Hiroshi FUJIWARA  Kei SHIBUSAWA  Kouki YAMAMOTO  Hiroaki YAMAMOTO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.3   pp.481-488
Publication Date: 2020/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019FCP0001
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Category: 
Keyword: 
online algorithm,  competitive analysis,  online optimization,  ski-rental problems,  

Full Text: PDF(377.6KB)>>
Buy this Article




Summary: 
The multislope ski-rental problem is an online optimization problem that generalizes the classical ski-rental problem. The player is offered not only a buy and a rent options but also other options that charge both initial and per-time fees. The competitive ratio of the classical ski-rental problem is known to be 2. In contrast, the best known so far on the competitive ratio of the multislope ski-rental problem is an upper bound of 4 and a lower bound of 3.62. In this paper we consider a parametric version of the multislope ski-rental problem, regarding the number of options as a parameter. We prove an upper bound for the parametric problem which is strictly less than 4. Moreover, we give a simple recurrence relation that yields an equation having a lower bound value as its root.