Analysis of Lower Bounds for the Multislope Ski-Rental Problem

Hiroshi FUJIWARA; Yasuhiro KONNO; Toshihiro FUJITO

doi:10.1587/transfun.E97.A.1200

Analysis of Lower Bounds for the Multislope Ski-Rental Problem

Hiroshi FUJIWARA, Yasuhiro KONNO, Toshihiro FUJITO

Full Text Views

0

Share
Cite this

Summary :

The 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1200-1205

Publication Date: 2014/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E97.A.1200

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Hiroshi FUJIWARA
  Toyohashi University of Technology
Yasuhiro KONNO
  Daisan Films Converting Co., Ltd.
Toshihiro FUJITO
  Toyohashi University of Technology

Keyword

online algorithm, competitive analysis, online optimization, ski-rental problems

Cite this

Copy

Hiroshi FUJIWARA, Yasuhiro KONNO, Toshihiro FUJITO, "Analysis of Lower Bounds for the Multislope Ski-Rental Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 6, pp. 1200-1205, June 2014, doi: 10.1587/transfun.E97.A.1200.
Abstract: The 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1200/_p

Copy

@ARTICLE{e97-a_6_1200,
author={Hiroshi FUJIWARA, Yasuhiro KONNO, Toshihiro FUJITO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Analysis of Lower Bounds for the Multislope Ski-Rental Problem},
year={2014},
volume={E97-A},
number={6},
pages={1200-1205},
abstract={The 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.},
keywords={},
doi={10.1587/transfun.E97.A.1200},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Analysis of Lower Bounds for the Multislope Ski-Rental Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1200
EP - 1205
AU - Hiroshi FUJIWARA
AU - Yasuhiro KONNO
AU - Toshihiro FUJITO
PY - 2014
DO - 10.1587/transfun.E97.A.1200
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - The 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.
ER -