Almost tight bounds for reordering buffer management
Almost tight bounds for reordering buffer management
复制标题
重新排序缓冲区管理的几乎严格限制
DOI：
10.1145/1993636.1993717
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Adamaszek A
中科院分区：
文献类型：
--
作者：
Adamaszek A
我们给出了在线重排序缓冲区管理问题在一致度量下的几乎紧界。具体地，我们通过证明确定性在线算法的竞争比至少为Ω(√(logk/loglogk})和随机化在线算法的竞争比至少为Ω(Loglogk)(其中k表示缓冲区的大小)，给出了该问题的第一个非平凡下界；我们通过给出重排序缓冲区管理问题的确定性在线算法来补充这一点，该算法获得O(√logk)的竞争比，几乎与下界匹配。这改进了Aigdor-Elgrabli和Rabani(Soda 2010)的算法，该算法实现了O(logk/loglogk)的竞争比。
We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically, we present the first non-trivial lower bounds for this problem by showing that deterministic online algorithms have a competitive ratio of at least Ω(√{log k/log log k}) and randomized online algorithms have a competitive ratio of at least Ω(log log k), where k denotes the size of the buffer.We complement this by presenting a deterministic online algorithm for the reordering buffer management problem that obtains a competitive ratio of O(√log k), almost matching the lower bound. This improves upon an algorithm by Avigdor-Elgrabli and Rabani (SODA 2010) that achieves a competitive ratio of O(log k/ log log k).
登录
查看更多内容
在线度量上排序缓冲区问题的在线和离线算法
DOI：
10.1016/j.jda.2008.08.002
发表时间：
2010
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
R. Khandekar;Vinayaka Pandit
通讯作者：
Vinayaka Pandit
重排序缓冲区问题的双标准近似
影响因子：
9.2
作者：
Siddharth Barman;Shuchi Chawla;S. Umboh
通讯作者：
S. Umboh
块设备的最佳在线缓冲区调度
DOI：
10.1145/2213977.2214031
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Adamaszek A
通讯作者：
Adamaszek A
改进了在线度量排序缓冲区问题的在线算法
DOI：
10.1145/1644015.1644030
发表时间：
2009
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
Iftah Gamzu;D. Segev
通讯作者：
D. Segev
一种用于重新排序缓冲区管理的最佳随机在线算法
DOI：
10.1109/focs.2013.9
发表时间：
2013
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
Noa Avigdor;Y. Rabani
通讯作者：
Y. Rabani