@inproceedings{bdaa600696744b0196739bf14a51a497,
title = "Almost tight bounds for reordering buffer management",
abstract = "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).",
keywords = "online algorithms, reordering buffer, sorting buffer",
author = "Anna Adamaszek and Artur Czumaj and Matthias Englert and Harald R{\"a}cke",
year = "2011",
doi = "10.1145/1993636.1993717",
language = "English",
isbn = "9781450306911",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "607--616",
booktitle = "STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing",
note = "43rd ACM Symposium on Theory of Computing, STOC 2011 ; Conference date: 06-06-2011 Through 08-06-2011",
}