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
다중슬로프 스키 대여 문제는 고전적인 스키 대여 문제를 일반화하는 온라인 최적화 문제입니다. 플레이어는 구매 및 임대 옵션뿐만 아니라 초기 및 시간당 비용을 모두 청구하는 기타 옵션도 제공됩니다. 고전적인 스키 렌탈 문제의 경쟁률은 2로 알려져 있습니다. 이와 대조적으로 멀티슬로프 스키 렌탈 문제의 경쟁률에 대해 지금까지 가장 잘 알려진 것은 상한은 4이고 하한은 3.62입니다. 본 논문에서 우리는 옵션 수를 매개변수로 사용하는 멀티슬로프 스키 대여 문제의 매개변수적 버전을 고려합니다. 우리는 4보다 엄격하게 작은 파라메트릭 문제의 상한을 증명합니다. 또한 하한 값을 루트로 갖는 방정식을 생성하는 간단한 반복 관계를 제공합니다.
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.
부
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
부
@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},}
부
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 -