A Bicriteria Approximation for the Reordering Buffer Problem
A Bicriteria Approximation for the Reordering Buffer Problem
复制标题
重排序缓冲区问题的双标准近似
DOI：
10.1007/978-3-642-33090-2_15
复制
发表时间：
2012
影响因子：
9.2
通讯作者：
S. Umboh
中科院分区：
文献类型：
--
作者：
Siddharth Barman;Shuchi Chawla;S. Umboh
在重新排序缓冲区问题（RBP）中，要求服务器处理位于度量空间中的请求序列。要处理请求，服务器必须移动到度量中的相应点。请求可以稍微打乱顺序处理；特别是，服务器有一个容量为k的缓冲区，在读取序列时可以存储多达k个请求。目标是以这样一种方式重新排序请求，即满足缓冲区约束并使服务器的总传输成本最小化。RBP出现在许多需要使用有限缓冲容量进行调度的应用程序中，例如在存储系统中调度磁盘臂，在汽车制造工厂的油漆车间切换颜色，以及在计算机图形中渲染3D图像。
In the reordering buffer problem (RBP), a server is asked to process a sequence of requests lying in a metric space. To process a request the server must move to the corresponding point in the metric. The requests can be processed slightly out of order; in particular, the server has a buffer of capacity k which can store up to k requests as it reads in the sequence. The goal is to reorder the requests in such a manner that the buffer constraint is satisfied and the total travel cost of the server is minimized. The RBP arises in many applications that require scheduling with a limited buffer capacity, such as scheduling a disk arm in storage systems, switching colors in paint shops of a car manufacturing plant, and rendering 3D images in computer graphics.
We study the offline version of RBP and develop bicriteria approximations. When the underlying metric is a tree, we obtain a solution of cost no more than 9 OPT using a buffer of capacity 4k+1 where OPT is the cost of an optimal solution with buffer capacity k. Via randomized tree embeddings, this implies an O(logn) approximation to cost and O(1) approximation to buffer size for general metrics. In contrast, when the buffer constraint is strictly enforced, constant-factor approximations are known only for the uniform metric (Avigdor-Elgrabli et al., 2012); the best known approximation ratio for arbitrary metrics is O(log2k logn) (Englert et al., 2007).
重新排序缓冲区管理的几乎严格限制
DOI：
10.1145/1993636.1993717
发表时间：
2011
期刊：
--
影响因子：
--
作者：
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.