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 pp following the service to a request qq requires the cost corresponding to the distance d(p,q)d(p,q) between pp and qq. 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)=1d(p,q)=1 if p≠qp≠q, d(p,q)=0d(p,q)=0 otherwise, and present the first NP-hardness proof for SBP on the uniform metric.