| 講演名 | 1997/3/17 kサーバ問題の一拡張とその最適戦略の計算複雑性 山家 明男, 櫻井 幸一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本研究では,オンラインモデルの一つであるkサーバ問題へ一つの要求に対して複数のサーバ(従来は一つのサーバ)が処理を行うように拡張した問題を扱う.我々は,この拡張kサーバ問題を二人ゼロ和ゲームとみなし,その純粋最適戦略の存在と計算複雑性を示した.これらの結果は,すでに最適戦略に関して様々な結果が知られている別のゲーム(Mean Payoff Game)[Ehrenfeucht and Mycielski,International Journal of Game Theory 8,pp.109-113(1979)]への変換によって得られたものである。計算複雑性に関する結果としては,我々の最適戦略を計算する方法では指数時間かつ指数領域かかることがわかったが,サーバの数が定数という仮定をつければ,非決定性多項式時間で計算可能であることを示した.また,同じ仮定の下でランダム要求に対する最適戦略は多項式時間で計算可能であることを示した. |
| 抄録(英) | We generalize the k-server problem, for which many competitive algorithms have been studied, by placing multiple servers at the requested vertex, and investigate this extended k-server problem from the game theoretic point of view as a two-person zero-sum game. We first show that the extended k-server problem has pure optimal strategies by translating it to mean payoff games introduced in [Ehrenfeucht and Mycielski, International Journal of Game Theory 8, pp. 109-113(1979)]. Next we consider the computational complexity of finding an optimal strategies for extended k-server problems. Though our method requires exponential time and exponential space to compute an optimal strategy of the extended k-server problem in the general cases, we show that an optimal strategy for k-server games is computed in non-deterministic polynomial-time assuming that the number of servers is C(or n-C), where n is the number of vertices and C is a constant. Moreover, we show that, under the same assumption above, our algorjthm for finding an optimal strategy for extended k-server games against random requests can be executed in polynomial-time. |
| キーワード(和) | kサーバ問題 / Mean Payoff Game / 最適戦略 / ゲーム理論 / オンラインアルゴリズム / 競合比 / 計算複雑性 |
| キーワード(英) | k-server problem / mean payoff game / optimal strategy / game theory / on-line algorithms / competitive ratio / computational complexity |
| 資料番号 | COMP96-85 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1997/3/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | kサーバ問題の一拡張とその最適戦略の計算複雑性 |
| サブタイトル（和） | |
| タイトル（英） | An Extension of On-line k-server Problems And Its Game-theoretic Computational Complexity |
| サブタイトル（和） | |
| キーワード(1)（和/英） | kサーバ問題 / k-server problem |
| キーワード(2)（和/英） | Mean Payoff Game / mean payoff game |
| キーワード(3)（和/英） | 最適戦略 / optimal strategy |
| キーワード(4)（和/英） | ゲーム理論 / game theory |
| キーワード(5)（和/英） | オンラインアルゴリズム / on-line algorithms |
| キーワード(6)（和/英） | 競合比 / competitive ratio |
| キーワード(7)（和/英） | 計算複雑性 / computational complexity |
| 第 1 著者 氏名（和/英） | 山家 明男 / Akio YANBE |
| 第 1 著者 所属（和/英） | 九州大学大学院 システム情報科学研究科 情報工学専攻 Department of Computer Science and Communication Engineering, Kyushu University |
| 第 2 著者 氏名（和/英） | 櫻井 幸一 / Kouichi SAKURAI |
| 第 2 著者 所属（和/英） | 九州大学大学院 システム情報科学研究科 情報工学専攻 Department of Computer Science and Communication Engineering, Kyushu University |
| 発表年月日 | 1997/3/17 |
| 資料番号 | COMP96-85 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 585 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |