多状態スキーレンタル問題に対する最適競合比の解析
スポンサーリンク
概要
- 論文の詳細を見る
古典的スキーレンタル問題 11) を一般化した多状態スキーレンタル問題 12) について研究する.プレーヤーにはレンタルか購入の選択肢に加え,初期費用と単位時間毎の両方の料金を支払う選択肢が与えられる.我々は,与えられたインスタンスに対し達成可能な最適戦略の競合比を最適競合比として定義する.そして任意のインスタンスに対し,最適競合比の上限と下限を解析する.下限はプレーヤーにとって最も有利なインスタンスが選ばれたとき,どれだけ良い競合比が達成可能かを示す.一方,上限はいわゆる競合比についての一致する上下界を意味する.我々は,この最適競合比の下限は,プレーヤーの選択肢の数を k +1 個とすると (k +1)k/((k +1)k -kk) であることを示した.このことは,いかなるインスタンスに対し最適戦略をとっても,競合比は e/(e - 1) より小さくできないことを意味している.また,状態数を 3 つに限定したものに対し,上限は 2.47,選択肢を 4 つに限定したものに対し,上限は 2.75 であることも示す.
- 2011-01-05
著者
関連論文
- 1-B-4 オフライン・オンライン混合ジョブスケジューリング問題に対するラグランジュ緩和法(スケジューリング(1))
- 1-F-2 オンライン・オフライン混合ジョブスケジューリング問題(生産・物流)
- LA-001 A New Approach to Approximate the Collision Probability in an Automated Production Line
- 1-E-9 生産ラインにおける衝突確率 : 処理時間がアーラン分布に従う場合(待ち行列)
- 多状態スキーレンタル問題に対する最適競合比の解析
- 正多角形領域に対するオンライン追跡問題
- レンタルスキー問題に対する平均的競合比の解析
- d-claw freeグラフ上の独立集合問題に対する局所探索法について
- 層別グラフにおける有向木被覆問題の近似について (理論計算機科学の深化と応用)
- 最小コスト木状被覆問題の2倍近似アルゴリズム
- 重みつき集合充填問題に対する局所改善法について
- 集合多重被覆問題に対する貪欲法の改良
- 2011年度冬のLAシンポジウム Approximating Steiner Tree and Tree Cover problems in Directed Graphs (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)
- 木状泥棒領域を持つグラフ護衛問題の近似
- 木状泥棒領域を持つグラフ護衛問題の近似
- 初等的二部グラフで構成される木における恒久的頂点被覆数について(一般)