WEKO3
アイテム
多状態スキーレンタル問題に対する最適競合比の解析
https://ipsj.ixsq.nii.ac.jp/records/71721
https://ipsj.ixsq.nii.ac.jp/records/71721aae3a31c-9489-4e0a-b672-330fe0fc97aa
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2011 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2011-01-05 | |||||||
タイトル | ||||||||
タイトル | 多状態スキーレンタル問題に対する最適競合比の解析 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Analysis of the Best Possible Competitive Ratio for Multislope Ski Rental | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
豊橋技術科学大学 | ||||||||
著者所属 | ||||||||
豊橋技術科学大学 | ||||||||
著者所属 | ||||||||
豊橋技術科学大学 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Toyohashi University of Technology | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Toyohashi University of Technology | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Toyohashi University of Technology | ||||||||
著者名 |
北野, 琢麻
× 北野, 琢麻
|
|||||||
著者名(英) |
Takuma, Kitano
× Takuma, Kitano
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 古典的スキーレンタル問題 11) を一般化した多状態スキーレンタル問題 12) について研究する.プレーヤーにはレンタルか購入の選択肢に加え,初期費用と単位時間毎の両方の料金を支払う選択肢が与えられる.我々は,与えられたインスタンスに対し達成可能な最適戦略の競合比を最適競合比として定義する.そして任意のインスタンスに対し,最適競合比の上限と下限を解析する.下限はプレーヤーにとって最も有利なインスタンスが選ばれたとき,どれだけ良い競合比が達成可能かを示す.一方,上限はいわゆる競合比についての一致する上下界を意味する.我々は,この最適競合比の下限は,プレーヤーの選択肢の数を k +1 個とすると (k +1)k/((k +1)k -kk) であることを示した.このことは,いかなるインスタンスに対し最適戦略をとっても,競合比は e/(e - 1) より小さくできないことを意味している.また,状態数を 3 つに限定したものに対し,上限は 2.47,選択肢を 4 つに限定したものに対し,上限は 2.75 であることも示す. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The multislope ski-rental problem12) is an extension of the classical ski-rental problem11), where the player has the options of leasing skis by paying both the per-time and the initial fees, in addition to renting and buying options. We define the best possible competitive ratio as the competitive ratio of the best strategy for a given instance, and analyze its infimum and supremum over arbitrary instances. The infimum indicates how much the competitive ratio is improved when the best instance and the best strategy are taken. On the other hand, the supremum is equivalent to a matching upper and lower bound of the competitive ratio. We prove that for the (k + 1)-slope problem, the infimum is (k + 1)k/((k + 1)k - kk), which implies that no matter how many options the player has, the competitive ratio can be no better than e/(e - 1) ≈ 1.58. We also show that the supremum is 2.47 for k = 2 and 2.75 for k = 3, which is the first matching bound for each. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
研究報告アルゴリズム(AL) 巻 2011-AL-133, 号 6, p. 1-8, 発行日 2011-01-05 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |