Almost tight bounds for reordering buffer management
Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke · 2011
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.