ALMOST TIGHT BOUNDS FOR REORDERING BUFFER MANAGEMENT

We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically, we present the first nontrivial 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 that achieves a competitive ratio of O(log k/ log log k).