NP-hardness of the sorting buffer problem on the uniform metric ?
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 p following the service to a request q q requires the cost corresponding to the distance d(p,q) d ( p , q ) between p p and q 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 d ( p , q ) = 1 if p?q p ? q , d(p,q)=0 d ( p , q ) = 0 otherwise, and present the first NP-hardness proof for SBP on the uniform metric.
np-hardness sorting buffer problem uniform metric metric space