A note on sorting buffers offline
A note on sorting buffers offline
复制标题
关于离线排序缓冲区的注意事项
DOI：
10.1016/j.tcs.2011.12.077
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
R. van Stee.
中科院分区：
文献类型：
--
作者：
H.-L. Chan;N. Megow;R. Sitters;R. van Stee.
我们考虑离线排序缓冲区问题。输入是一系列不同类型的项。所有项目必须由服务器逐个处理。服务器配备了一个容量有限的随机访问缓冲区，可用于重新排列项目。问题是设计一个调度策略，决定从缓冲区中的项目发送到服务器的顺序。每个类型的变化会产生单位成本，因此，目标是最小化服务于整个序列的类型变化的总数。这个问题是由制造过程和计算机科学中的各种应用所激发的，并且在过去几年中引起了极大的关注。主要的焦点是在线竞争算法。令人惊讶的是，人们对基本的离线问题知之甚少。在本文中，我们证明了具有均匀成本的排序缓冲区问题是NP-困难的，从而关闭了离线问题的最基本的问题之一。在积极的一面，我们给出了一个O（1）-近似算法时，调度程序的缓冲区仅略大于原来的大小的两倍。我们还勾画了一个快速的动态规划算法的特殊情况下的缓冲区大小为2。
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 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 sketch a fast dynamic programming algorithm for the special case of buffer size 2.
在线度量上排序缓冲区问题的在线和离线算法
DOI：
10.1016/j.jda.2008.08.002
发表时间：
2010
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
R. Khandekar;Vinayaka Pandit
通讯作者：
Vinayaka Pandit
重新排序缓冲区管理的几乎严格限制
DOI：
10.1145/1993636.1993717
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Adamaszek A
通讯作者：
Adamaszek A