Computer Science – Data Structures and Algorithms
Scientific paper
2010-09-22
Computer Science
Data Structures and Algorithms
14 pages
Scientific paper
We consider the offline sorting buffer problem. The input is a sequence of items of different types. All items must be processed one by one by a server. The server is equipped with a random-access buffer of limited capacity which can be used to rearrange items. The problem is to design a scheduling strategy that decides upon the order in which items from the buffer are sent to the server. Each type change incurs unit cost, and thus, the cost minimizing objective is to minimize the total number of type changes for serving the entire sequence. This problem is motivated by various applications in manufacturing processes and computer science, and it has attracted significant attention in the last few years. The main focus has been on online competitive algorithms. Surprisingly little is known on the basic offline problem. In this paper, we show that the sorting buffer problem with uniform cost is NP-hard and, thus, close one of the most fundamental questions for the offline problem. On the positive side, we give an O(1)-approximation algorithm when the scheduler is given a buffer only slightly larger than double the original size. We also give a dynamic programming algorithm for the special case of buffer size two that solves the problem exactly in linear time, improving on the standard DP which runs in cubic time.
Chan Ho-Leung
Megow Nicole
Sitters Rene
Stee Rob van
No associations
LandOfFree
The Sorting Buffer Problem is NP-hard does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Sorting Buffer Problem is NP-hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Sorting Buffer Problem is NP-hard will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-637905