Item type |
学術雑誌論文 / Journal Article(1) |
公開日 |
2018-03-09 |
タイトル |
|
|
タイトル |
Analysis of Lower Bounds for the Multislope Ski-Rental Problem |
言語 |
|
|
言語 |
eng |
DOI |
|
|
|
関連識別子 |
https://doi.org/10.1587/transfun.E97.A.1200 |
|
|
関連名称 |
10.1587/transfun.E97.A.1200 |
キーワード |
|
|
主題 |
online algorithm, competitive analysis, online optimization, ski-rental problems |
資源タイプ |
|
|
資源 |
http://purl.org/coar/resource_type/c_6501 |
|
タイプ |
journal article |
著者 |
Fujiwara, Hiroshi
Konno, Yasuhiro
Fujito, Toshihiro
|
信州大学研究者総覧へのリンク |
|
|
氏名 |
Fujiwara, Hiroshi |
|
URL |
http://soar-rd.shinshu-u.ac.jp/profile/ja.OmSVOFnU.html |
出版者 |
|
|
出版者 |
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG |
引用 |
|
|
内容記述 |
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES. E97A(6): 1200-1205 (2014) |
書誌情報 |
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
巻 E97A,
号 6,
p. 1200-1205,
発行日 2014
|
抄録 |
|
|
内容記述 |
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. |
資源タイプ(コンテンツの種類) |
|
|
内容記述 |
Article |
ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1745-1337 |
権利 |
|
|
権利情報 |
copyright©2014 IEICE |
出版タイプ |
|
|
出版タイプ |
VoR |
|
出版タイプResource |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
WoS |
|
|
URL |
http://gateway.isiknowledge.com/gateway/Gateway.cgi?&GWVersion=2&SrcAuth=ShinshuUniv&SrcApp=ShinshuUniv&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000342738600007 |