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 non-uniform cost. A reordering buffer which is a random access buffer with storage capacity for k objects can be used to rearrange this sequence in such a way that the total cost are minimized. This concept is useful for many applications in computer science and economics.
We show that a reordering buffer reduces the cost of each sequence by a factor of at most 2k–1. This result even holds for cost functions modeled by arbitrary metric spaces. In addition, a matching lower bound is presented. From this bound follows that each strategy that does not increase the cost of a sequence is at least (2k–1)-competitive.
As main result, we present the deterministic Maximum Adjusted Penalty (MAP) strategy which is O(log k)-competitive. Previous strategies only achieve a competitive ratio of k in the non-uniform model. For the upper bound on MAP, we introduce a basic proof technique. We believe that this technique can be interesting for other problems.
Supported by the DFG grant WE 2842/1.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
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
Teorey, T., Pinkerton, T.: A comparative analysis of disk scheduling policies. Communications of the ACM 15, 177–184 (1972)
Fiat, A., Karp., R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E.: Competitive paging algorithms. Journal of Algorithms 12, 685–699 (1991)
Albers, S.: New results on web caching with request reordering. In: Proceedings of the 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 84–92 (2004)
Feder, T., Motwani, R., Panigrahy, R., Seiden, S., van Stee, R., Zhu, A.: Combining request scheduling with web caching. Theoretical Compuer Science 324, 201–218 (2004)
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)
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)
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)
Gutenschwager, K., Spieckermann, S., Voss, S.: A sequential ordering problem in automotive paint shops. International Journal of Production Research 42, 1865–1878 (2004)
Yeh, T., Kuo, C., Lei, C., Yen, H.: Competitive analysis of on-line disk scheduling. Theory of Computing Systems 31, 491–506 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Englert, M., Westermann, M. (2005). Reordering Buffer Management for Non-uniform Cost Models. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds) Automata, Languages and Programming. ICALP 2005. Lecture Notes in Computer Science, vol 3580. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11523468_51
Download citation
DOI: https://doi.org/10.1007/11523468_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27580-0
Online ISBN: 978-3-540-31691-6
eBook Packages: Computer ScienceComputer Science (R0)