kサーバ問題の一拡張とその最適戦略の計算複雑性

概要

論文の詳細を見る
本研究では,オンラインモデルの一つであるkサーバ問題へ一つの要求に対して複数のサーバ(従来は一つのサーバ)が処理を行うように拡張した問題を扱う.我々は,この拡張kサーバ問題を二人ゼロ和ゲームとみなし,その純粋最適戦略の存在と計算複雑性を示した.これらの結果は,すでに最適戦略に関して様々な結果が知られている別のゲーム(Mean Payoff Game)[Ehrenfeucht and Mycielski,International Journal of Game Theory 8,pp.109-113(1979)]への変換によって得られたものである。計算複雑性に関する結果としては,我々の最適戦略を計算する方法では指数時間かつ指数領域かかることがわかったが,サーバの数が定数という仮定をつければ,非決定性多項式時間で計算可能であることを示した.また,同じ仮定の下でランダム要求に対する最適戦略は多項式時間で計算可能であることを示した.
社団法人電子情報通信学会の論文
1997-03-17