一様メトリックにおけるソーティングバッファ問題の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困難となることを示す.%An instance of the sorting buffer problem consists of a sequence of requests for service each of which is specified by a point in a metric space, and a sorting buffer which can store up to a limited number of requests and rearrange them. To serve a request, the server needs to visit the request point where serving a request p following the service to a request q requires the cost corresponding to the distance d(p, q) between p and q. The objective of the sorting buffer problem is to serve all input requests in a way that minimizes the total distance traveled by the server in the metric space by reordering the input sequence. In this paper we focus our attention to the uniform metric, i.e., the distance d(p,q) = 1 if p ≠ q, d(p,q) = 0 otherwise. For the general setting, the sorting buffer problem is known to be NP-hard. For the uniform metric, however, it is not known if the problem remains NP-hard. In this paper, we present the first NP-hardness proof for the sorting buffer problem on the uniform metric.