Reordering Buffers for General Metric Spaces

by Matthias Englert, Harald Räcke, and Matthias Westermann

Theory of Computing, Volume 6(2), pp. 27-46, 2010

Bibliography with links to cited articles

[1]   Amjad Aboud: Correlation clustering with penalties and approximating the recordering buffer management problem. Master’s thesis, The Technion - Israel Institute of Technology, Janurary 2008. [Technion TR archive].

[2]   Houman Alborzi, Eric Torng, Patchrawat Uthaisombut, and Stephen Wagner: The k-client problem. J. Algorithms, 41(2):115–173, 2001. [doi:10.1006/jagm.2001.1182].

[3]   Noa Avigdor-Elgrabli and Yuval Rabani: An improved competitive algorithm for reordering buffer management. In Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 13–21. ACM Press, 2010.

[4]   Reuven Bar-Yehuda and Jonathan Laserson: Exploiting locality: Approximating sorting buffers. In Proc. 3rd Workshop on Approximation and Online Algorithms (WAOA), volume 3879 of Lecture Notes in Computer Science, pp. 69–81. Springer, 2005. [doi:10.1007/11671411_6].

[5]   Yair Bartal: Probabilistic approximations of metric spaces and its algorithmic applications. In Proc. 37th FOCS, pp. 184–193. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548477].

[6]   Yair Bartal: On approximating arbitrary metrics by tree metrics. In Proc. 30th STOC, pp. 161–168. ACM Press, 1998. [doi:10.1145/276698.276725].

[7]   Matthias Englert, Deniz Özmen, and Matthias Westermann: The power of reordering for online minimum makespan scheduling. In Proc. 49th FOCS, pp. 603–612. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.46].

[8]   Matthias Englert, Heiko Röglin, and Matthias Westermann: Evaluation of online strategies for reordering buffers. In Proc. 5th Internat. Workshop on Efficient and Experimental Algorithms (WEA), volume 4007 of Lecture Notes in Computer Science, pp. 183–194. Springer, 2006. [doi:10.1007/11764298_17].

[9]   Matthias Englert and Matthias Westermann: Reordering buffer management for non-uniform cost models. In Proc. 32nd Internat. Colloquium on Automata, Languages and Programming (ICALP), volume 3580 of Lecture Notes in Computer Science, pp. 627–638. Springer, 2005. [doi:10.1007/11523468_51].

[10]   Jittat Fakcharoenphol, Satish B. Rao, and Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004. [doi:10.1016/j.jcss.2004.04.011].

[11]   Iftah Gamzu and Danny Segev: Improved online algorithms for the sorting buffer problem. In Proc. 24th Symp. on Theoretical Aspects of Computer Science (STACS), volume 4393 of Lecture Notes in Computer Science, pp. 658–669. Springer, 2007. [doi:10.1007/978-3-540-70918-3_56].

[12]   Kai Gutenschwager, Sven Spiekermann, and Stefan Voß: A sequential ordering problem in automotive paint shops. Internat. J. Production Research, 42(9):1865–1878, 2004. [doi:10.1080/00207540310001646821].

[13]   Rohit Khandekar and Vinayaka Pandit: Online and offline algorithms for the sorting buffers problem on the line metric. J. Discrete Algorithms, 2008. [doi:10.1016/j.jda.2008.08.002].

[14]   Jens S. Kohrt and Kirk Pruhs: A constant factor approximation algorithm for sorting buffers. In Proc. 6th Latin American Symp. on Theoretical Informatics (LATIN), volume 2976 of Lecture Notes in Computer Science, pp. 193–202. Springer, 2004. [LATIN:fqbc84923gveuhlr].

[15]   Jens Krokowski, Harald Räcke, Christian Sohler, and Matthias Westermann: Reducing state changes with a pipeline buffer. In Proc. 9th Internat. Fall Workshop Vision, Modeling, and Visualization (VMV), pp. 217–224. Aka GmbH, 2004.

[16]   Harald Räcke, Christian Sohler, and Matthias Westermann: Online scheduling for sorting buffers. In Proc. 10th European Symp. on Algorithms (ESA), volume 2461 of Lecture Notes in Computer Science, pp. 820–832. Springer, 2002. [doi:10.1007/3-540-45749-6_71, ESA:mx7mdle1j62b5n3h].

[17]   Toby J. Teorey and Tad B. Pinkerton: A comparative analysis of disk scheduling policies. Comm. ACM, 15(3):177–184, 1972. [doi:10.1145/361268.361278].