NP-hardness of the sorting buffer problem on the uniform metric

• DOI: 10.1016/j.dam.2012.02.005
• Publication Date: 2012-03-06T04:09:13Z
• Authors: Yuichi Asahiro; Kenichi Kawahara; Eiji Miyano
• Keywords: Applied Mathematics; NP-hardness; Uniform metric; Discrete Mathematics and Combinatorics; 0102 computer and information sciences; Sorting buffer problem; Metric space; 01 natural sciences

AbstractAn 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.