Almost Tight Bounds for Reordering Buffer Management
April 13, 2011
ABSTRACT: In the reordering buffer management problem a stream of colored items arrives at a service station and has to be processed. The cost for servicing the items heavily depends on the processing order: servicing an item with color $c$, when the most recently serviced item had color $c'\neq c$, incurs a context switching cost $w_c$. In order to reduce the total processing cost, the service station is equipped with a reordering buffer able to store $k$ items. This buffer can be used to reorder the input sequence in a restricted fashion to construct an output sequence with lower processing cost. At each point in time, the buffer contains the first $k$ items of the input sequence that have not yet been processed. A scheduling strategy has to decide which item to service next. Upon its decision, the corresponding item is removed from the buffer and serviced, while the next item from the input sequence takes its place in the buffer.

Our results are as follows:
We present the first non-trivial lower bounds on the competitive ratio of online algorithms. Specifically, we show that any deterministic online algorithm for the reordering buffer management problem has a competitive ratio of at least $\Omega(\sqrt{\log k/\log \log k})$, even in the uniform case when $w_c=1$ for all colors $c$.
Next, we complement this lower bound by presenting a deterministic online algorithm for the reordering buffer management problem that obtains a competitive ratio of $O(\sqrt{\log k})$, almost matching the lower bound. This improves upon a recent algorithm by Avigdor-Elgrabli and Rabani (SODA 2010) which achieves a competitive ratio of $O(\log k/\log\log k)$.
Finally, we show a lower bound of $\Omega(\log\log k)$ on the competitive ratio of any \emph{randomized} online algorithm. In particular, our work provides the first proof that no online algorithm (either deterministic or randomized) for the reordering buffer management problem can achieve a constant competitive ratio.

Joint work with Anna Adamaszek, Artur Czumaj, and Harald Raecke.