
For FullText 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 SkiRental Problem
Hiroshi FUJIWARA Kei SHIBUSAWA Kouki YAMAMOTO Hiroaki YAMAMOTO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E103D
No.3
pp.481488 Publication Date: 2020/03/01
Online ISSN: 17451361
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, skirental problems,
Full Text: PDF(377.6KB)>>
Summary:
The multislope skirental problem is an online optimization problem that generalizes the classical skirental problem. The player is offered not only a buy and a rent options but also other options that charge both initial and pertime fees. The competitive ratio of the classical skirental problem is known to be 2. In contrast, the best known so far on the competitive ratio of the multislope skirental 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 skirental 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.

