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.

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.