Abstract

An Almost Tight Bound for Reordering Buffer Management

Harald Räecke
University of Warwick

In the reordering buffer problem, we are given an input sequence of requests for service each of which corresponds to a point in a metric space. The cost of serving the requests heavily depends on the processing order. Serving a request
induces cost corresponding to the distance between itself and the previously served request, measured in the underlying metric space. A reordering buffer with storage capacity $k$ can be used to reorder the input sequence in a
restricted fashion so as to construct an output sequence with lower service cost. This simple and universal framework is useful for many applications in computer science and economics, e.g., disk scheduling, rendering in computer
graphics, or painting shops in car plants.

We present the first non-constant lower bound on the competitive ratio of determinstic online algorithms for the reordering buffer problem in a uniform metric. Precisely, we show that any online algorithm for the problem has a
competitive ratio of $\Omega(\sqrt{\log k/\log\logk})$. We complement this result by presenting a determinstic online algorithm that
obtains a competitive ratio of $O(\sqrt{\log k})$ for the problem. This improves upon an algorithm by Avigdor-Elgrabli and Rabani [SODA 2010] that
obtained a competitive ratio of $O(\log k/\log\logk)$.