The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
O problema do aluguel de esquis multipistas é um problema de otimização online que generaliza o problema clássico do aluguel de esquis. Ao jogador são oferecidas não apenas opções de compra e aluguel, mas também outras opções que cobram taxas iniciais e por tempo. Sabe-se que o rácio competitivo do problema clássico do aluguer de esquis é 2. Em contraste, o mais conhecido até agora sobre o rácio competitivo do problema do aluguer de esquis multipistas é um limite superior de 4 e um limite inferior de 3.62. Neste artigo consideramos uma versão paramétrica do problema de aluguel de esquis multipistas, tendo como parâmetro o número de opções. Provamos um limite superior para o problema paramétrico que é estritamente menor que 4. Além disso, fornecemos uma relação de recorrência simples que produz uma equação tendo um valor de limite inferior como raiz.
Hiroshi FUJIWARA
Shinshu University
Kei SHIBUSAWA
Shinshu University
Kouki YAMAMOTO
Shinshu University
Hiroaki YAMAMOTO
Shinshu University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Hiroshi FUJIWARA, Kei SHIBUSAWA, Kouki YAMAMOTO, Hiroaki YAMAMOTO, "Bounds for the Multislope Ski-Rental Problem" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 3, pp. 481-488, March 2020, doi: 10.1587/transinf.2019FCP0001.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019FCP0001/_p
Copiar
@ARTICLE{e103-d_3_481,
author={Hiroshi FUJIWARA, Kei SHIBUSAWA, Kouki YAMAMOTO, Hiroaki YAMAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Bounds for the Multislope Ski-Rental Problem},
year={2020},
volume={E103-D},
number={3},
pages={481-488},
abstract={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.},
keywords={},
doi={10.1587/transinf.2019FCP0001},
ISSN={1745-1361},
month={March},}
Copiar
TY - JOUR
TI - Bounds for the Multislope Ski-Rental Problem
T2 - IEICE TRANSACTIONS on Information
SP - 481
EP - 488
AU - Hiroshi FUJIWARA
AU - Kei SHIBUSAWA
AU - Kouki YAMAMOTO
AU - Hiroaki YAMAMOTO
PY - 2020
DO - 10.1587/transinf.2019FCP0001
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2020
AB - 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.
ER -