NP-hardness of the Sorting Buffer Problem on the Uniform Metric
NP-hardness of the Sorting Buffer Problem on the Uniform Metric
复制标题
统一度量上排序缓冲区问题的 NP 难度
DOI：
10.1016/j.dam.2012.02.005
复制
发表时间：
2012
影响因子：
1.1
通讯作者：
and Eiji Miyano
中科院分区：
文献类型：
--
作者：
Yuichi Asahiro;Kenichi Kawahara;and Eiji Miyano
排序缓冲区问题（SBP）的一个例子包括一系列的服务请求，其中每个请求都由一个度量空间中的一个点指定，以及一个可以存储有限数量的请求并重新排列它们的排序缓冲区。为了服务于请求，服务器需要访问在服务于请求q之后服务于请求p需要对应于p和q之间的距离d（p，q）的成本的点。SBP的目标是通过重新排序输入序列，以最小化服务器行进的总距离的方式服务所有输入请求。在本文中，我们把我们的注意力集中在一致度量，即，当p≠q时，距离d（p，q）=1，否则d（p，q）=0，并给出了SBP在一致度量上的第一个NP-困难证明.
An instance of the sorting buffer problem (SBP) 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 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 SBP is to serve all input requests in a way that minimizes the total distance traveled by the server 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, and present the first NP-hardness proof for SBP on the uniform metric.