A sequence of objects which are characterized by their color has to be processed. Their processing order influences how efficiently
they can be processed: Each color change between two consecutive objects produces costs. A reordering buffer which is a random
access buffer with storage capacity for k objects can be used to rearrange this sequence online in such a way that the total costs are reduced. This concept is useful
for many applications in computer science and economics.
The strategy with the best known competitive ratio is MAP. An upper bound of
O(log
k) on the competitive ratio of MAP is known and a non-constant lower bound on the competitive ratio is not known [2]. Based
on theoretical considerations and experimental evaluations, we give strong evidence that the previously used proof techniques
are not suitable to show an
o(Ö{logk})o(\sqrt{\log k}) upper bound on the competitive ratio of MAP. However, we also give some evidence that in fact MAP achieves a competitive
ratio of
O(1).
Further, we evaluate the performance of several strategies on random input sequences experimentally. MAP and its variants
RC and RR clearly outperform the other strategies FIFO, LRU, and MCF . In particular, MAP, RC, and RR are the only known strategies
whose competitive ratios do not depend on the buffer size. Furthermore, MAP achieves the smallest constant competitive ratio.
The first and the last author are supported by the DFG grant WE 2842/1. The second author is supported by the DFG grant VO
889/2.