@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",

}