An optimal randomized online algorithm for reordering buffer management
An optimal randomized online algorithm for reordering buffer management
复制标题
一种用于重新排序缓冲区管理的最佳随机在线算法
DOI：
10.1109/focs.2013.9
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Y. Rabani
中科院分区：
文献类型：
--
作者：
Noa Avigdor;Y. Rabani
我们给出了一个O（log log k）-竞争的随机在线算法的缓冲区管理，其中k是缓冲区的大小。我们的界限与Adamaszek等人的下限相匹配（STOC 2011）。我们的算法有两个阶段，并行在线执行。第一阶段确定性地计算用于重排序缓冲器管理的LP松弛的可行分数解。第二阶段使用随机性对分数解进行“舍入”。第一阶段是基于在线原始-对偶模式，结合对偶拟合收费方案。由于原始-对偶步骤和对偶拟合步骤是交错的，并且在某种意义上是冲突的，因此组合它们是具有挑战性的。我们还注意到，我们应用原始对偶模式的混合包装和覆盖约束的松弛。第一阶段产生分数LP解决方案，其成本在最优LP成本的O（log log k）的因子内。第二阶段是一个在线算法，将任何LP解决方案转换为积分解决方案，同时增加一个常数因子的成本。这一阶段概括了最近的结果，给出了一个类似的近似保证使用离线舍入算法。
We give an O(log log k)-competitive randomized online algorithm for reordering buffer management, where k is the buffer size. Our bound matches the lower bound of Adamaszek et al. (STOC 2011). Our algorithm has two stages which are executed online in parallel. The first stage computes deterministically a feasible fractional solution to an LP relaxation for reordering buffer management. The second stage "rounds" using randomness the fractional solution. The first stage is based on the online primal-dual schema, combined with a dual fitting charging scheme. As primal-dual steps and dual fitting steps are interleaved and in some sense conflicting, combining them is challenging. We also note that we apply the primal-dual schema to a relaxation with mixed packing and covering constraints. The first stage produces a fractional LP solution with cost within a factor of O(log log k) of the optimal LP cost. The second stage is an online algorithm that converts any LP solution to an integral solution, while increasing the cost by a constant factor. This stage generalizes recent results that gave a similar approximation guarantee using an offline rounding algorithm.