A Constant Factor Approximation Algorithm for Reordering Buffer Management
A Constant Factor Approximation Algorithm for Reordering Buffer Management
复制标题
重排序缓冲区管理的常数因子近似算法
DOI：
10.1137/1.9781611973105.70
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Y. Rabani
中科院分区：
文献类型：
--
作者：
Noa Avigdor;Y. Rabani
在重排序缓冲区管理问题（RBM）中，n个有色项的序列进入具有有限容量k的缓冲区。当缓冲区已满时，将一个项移到输出序列中，为下一个输入项腾出空间。重复此步骤，直到输入序列耗尽且缓冲器为空。目标是找到一个去除序列，使输出序列中颜色变化的总数最小化。该问题形式化了计算机和生产系统中的许多应用，并且被称为NP难问题。
给出了RBM的第一常数因子逼近保证。我们的算法是基于一个复杂的“舍入”的LP松弛RBM的解决方案，所以它也建立了一个恒定的上限上的完整性差距，这种松弛。我们的结果改进了Adamaszek等人（STOC 2011）使用不同方法并给出在线算法的O（log k）的最佳前界。我们的常数因子近似击败了Adamaszek等人给出的竞争比上的超常数下界。这是RBM的多项式时间离线算法的第一次演示，该算法可证明优于任何在线算法。
In the reordering buffer management problem (RBM) a sequence of n colored items enters a buffer with limited capacity k. When the buffer is full, one item is removed to the output sequence, making room for the next input item. This step is repeated until the input sequence is exhausted and the buffer is empty. The objective is to find a sequence of removals that minimizes the total number of color changes in the output sequence. The problem formalizes numerous applications in computer and production systems, and is known to be NP-hard.
We give the first constant factor approximation guarantee for RBM. Our algorithm is based on an intricate "rounding" of the solution to an LP relaxation for RBM, so it also establishes a constant upper bound on the integrality gap of this relaxation. Our results improve upon the best previous bound of O(√ log k) of Adamaszek et al. (STOC 2011) that used different methods and gave an online algorithm. Our constant factor approximation beats the super-constant lower bounds on the competitive ratio given by Adamaszek et al. This is the first demonstration of a polynomial time offline algorithm for RBM that is provably better than any online algorithm.
重新排序缓冲区管理的几乎严格限制
DOI：
10.1145/1993636.1993717
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Adamaszek A
通讯作者：
Adamaszek A
块设备的最佳在线缓冲区调度
DOI：
10.1145/2213977.2214031
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Adamaszek A
通讯作者：
Adamaszek A
关于离线排序缓冲区的注意事项
DOI：
10.1016/j.tcs.2011.12.077
发表时间：
--
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
H.-L. Chan;N. Megow;R. Sitters;R. van Stee.
通讯作者：
R. van Stee.