文献

J-GLOBAL ID：201102206794831340   整理番号：11A0663176

多状態スキーレンタル問題に対する最適競合比の解析

Analysis of the Best Possible Competitive Ratio for Multislope Ski Rental

著者 (3件)： 北野琢麻 (豊橋技科大) ,  藤原洋志 (豊橋技科大) ,  藤戸敏弘 (豊橋技科大)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2010  号： 5  ページ： ROMBUNNO.AL-133,NO.6  発行年： 2011年02月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 古典的スキーレンタル問題を一般化した多状態スキーレンタル問題について研究する。プレーヤーにはレンタルか購入の選択肢に加え,初期費用と単位時間毎の両方の料金を支払う選択肢が与えられる。我々は,与えられたインスタンスに対し達成可能な最適戦略の競合比を最適競合比として定義する。そして任意のインスタンスに対し,最適競合比の上限と下限を解析する。下限はプレーヤーにとって最も有利なインスタンスが選ばれたとき,どれだけ良い競合比が達成可能かを示す。一方,上限はいわゆる競合比についての一致する上下界を意味する。我々は,この最適競合比の下限は,プレーヤーの選択肢の数をk+1個とすると(k+1)^k/((k+1)^k-k^k)であることを示した。このことは,いかなるインスタンスに対し最適戦略をとっても,競合比はe/(e-1)より小さくできないことを意味している。また,状態数を3つに限定したものに対し,上限は2.47,選択肢を4つに限定したものに対し,上限は2.75であることも示す。(著者抄録)

シソーラス用語： *最適化問題 ,  *選択問題 ,  選択 ,  比率 ,  最適化 ,  最適化手法 ,  上限 ,  数学的性質
準シソーラス用語： 競合比 ,  最適戦略 ,  選択肢 ,  *多状態スキーレンタル問題

分類 (1件)： その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (4件)： スキー ,  レンタル ,  競合比 ,  解析