WEA 2006: Experimental Algorithms pp 183-194

Evaluation of Online Strategies for Reordering Buffers

• Matthias Englert
• Heiko Röglin
• Matthias Westermann
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4007)

Abstract

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(\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.

Keywords

Color Change Input Sequence Time Stamp Competitive Ratio Output Sequence
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

1. 1.
Bar-Yehuda, R., Laserson, J.: 9-approximation algorithm for sorting buffers. In: Proceedings of the 3rd Workshop on Approximation and Online Algorithms (2005)Google Scholar
2. 2.
Englert, M., Westermann, M.: Reordering buffer management for non-uniform cost models. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 627–638. Springer, Heidelberg (2005)
3. 3.
Gutenschwager, K., Spieckermann, S., Voss, S.: A sequential ordering problem in automotive paint shops. International Journal of Production Research 42(9), 1865–1878 (2004)
4. 4.
Khandekar, R., Pandit, V.: Online sorting buffers on line. In: Proceedings of the 23th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 584–595 (2006)Google Scholar
5. 5.
Kohrt, J., Pruhs, K.: A constant approximation algorithm for sorting buffers. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 193–202. Springer, Heidelberg (2004)
6. 6.
Krokowski, J., Räcke, H., Sohler, C., Westermann, M.: Reducing state changes with a pipeline buffer. In: Proceedings of the 9th International Fall Workshop Vision, Modeling, and Visualization (VMV), pp. 217–224 (2004)Google Scholar
7. 7.
Räcke, H., Sohler, C., Westermann, M.: Online scheduling for sorting buffers. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 820–832. Springer, Heidelberg (2002)

Authors and Affiliations

• Matthias Englert
• 1
• Heiko Röglin
• 1
• Matthias Westermann
• 1
1. 1.Department of Computer ScienceRWTH AachenAachenGermany