Almost Tight Bounds for Reordering Buffer Management

In this talk we will study the nowadays classical online problem of buffer reordering. 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' <> c, incurs a context switching cost w_c.

In order to reduce the total processing cost, the servicing station is equipped with a reordering bu ffer able to store k items. This buff er 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 buff er and serviced, while the next item from the input sequence takes its place in the buffer.

In this talk I'll present almost tight bounds for the online reordering buffer management problem on the uniform metric.

This is a joint work with Anna Adamaszek, Matthias Englert, and Harald Raecke.