一様メトリックにおけるソーティングバッファ問題のNP困難性

概要

論文の詳細を見る
ソーティングバッファ問題の入力は,メトリックスペース上の頂点で表された要求の列,それらの要求に応えるために頂点から頂点へと移動を行うサーバ,ある個数以下の要求を記憶することができるソーティングバッファである.要求に応えるためにサーバは頂点を訪れる必要があり,頂点p∈Vから頂点q∈Vに移動を行ったときのコストをpとqの距離d(p,q)であるとする.ソーティングバッファは要求列の順序を入れ換えるために用いられる.ソーティングバッファ問題の目的は,要求列の一部をソーティングバッファに記憶して要求列の順序を入れ換えることにより,すべての要求に応えるときのサーバの移動距離(コスト)を最小化することである.本稿では一様メトリック,すなわちp≠qのときd(p,q)=1となり,p=qならばd(p,q)=0となる場合について考える.一般のメトリックの場合には,ソーティングバッファ問題はNP困難となることが知られている.しかし,一様メトリックにおけるソーティングバッファの計算複雑さについては,NP困難になるかどうかが知られていなかった.本稿では,一様メトリックにおけるソーティングバッファ問題がNP困難となることを示す.
社団法人電子情報通信学会の論文
2008-05-06