For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Bounds for the Multislope Ski-Rental Problem
Hiroshi FUJIWARA Kei SHIBUSAWA Kouki YAMAMOTO Hiroaki YAMAMOTO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2020/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
online algorithm, competitive analysis, online optimization, ski-rental problems,
Full Text: PDF(377.6KB)>>
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.