Reordering buffers for general metric spaces

ABSTRACT

In the reordering buffer problem, we are given an input sequence of requests for service each of which corresponds to a point in a metric space. The cost of serving the requests heavily depends on the processing order. Serving a request induces cost corresponding to the distance between itself and the previously served request, measured in the underlying metric space. A reordering buffer with storage capacity k can be used to reorder the input sequence in a restricted fashion so as to construct an output sequence with lower service cost. This simple and universal framework is useful for many applications in computer science and economics, e.g., disk scheduling, rendering in computer graphics, or painting shops in car plants.

In this paper, we design online algorithms for the reordering buffer problem. Our main result is a strategy with a polylogarithmic competitive ratio for general metric spaces. Previous work on the reordering buffer problem only considered very restricted metric spaces. We obtain our result by first developing a deterministic algorithm for arbitrary weighted trees with a competitive ratio of O(D · log k), where D denotes the unweighted diameter of the tree, i.e., the maximum number of edges on a path connecting two nodes. Then we show how to improve this competitive ratio to O(log² k) for metric spaces that are derived from HSTs. Combining this result with the results on probabilistically approximating arbitrary metrics by tree metrics, we obtain a randomized strategy for general metric spaces that achieves a competitive ratio of O(log² k · log n) in expectation against an oblivious adversary. Here n denotes the number of distinct points in the metric space. Note that the length of the input sequence can be much larger than n.

REFERENCES

• 1: Houman Alborzi , Eric Torng , Patchrawat Uthaisombut , Stephen Wagner, The k-client problem, Journal of Algorithms, v.41 n.2, p.115-173, November 2001 [doi>10.1006/jagm.2001.1182 ]
• 2: R. Bar-Yehuda and JLaserson. Exploiting locality: Approximating sorting buffers. In Proceedings of the 3rd Workshop on Approximation and Online Algorithms (WAOA), pages 69--81, 2005.
• 3: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 4: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 5: M. Englert, H. Röglin, and M. Westermann. Evaluation of online strategies for reordering buffers. In Proceedings of the 5th International Workshop on Efficient and Experimental Algorithms (WEA), pages 183--194, 2006.
• 6: M. Englert and M. Westermann. Reordering buffer management for non-uniform cost models. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), pages 627--638, 2005.
• 7: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004 [doi>10.1016/j.jcss.2004.04.011]
• 8: I. Gamzu and D. Segev. Improved online algorithms for the sorting buffer problem. In Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science (STACS), pages 658--669, 2007.
• 9: K. Gutenschwager, S. Spiekermann, and S. Voş. A sequential ordering problem in automotive paint shops. International Journal of Production Research, 42(9):1865--1878, 2004.
• 10: R. Khandekar and V. Pandit. Offline sorting buffers on line. In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC), pages 81--89, 2006.
• 11: R. Khandekar and V. Pandit. Online sorting buffers on line. In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS), pages 584--595, 2006.
• 12: J.S. Kohrt and K. Pruhs. A constant factor approximation algorithm for sorting buffers. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN), pages 193--202, 2004.
• 13: J. Krokowski, H. Räcke, C. Sohler, and M. Westermann. Reducing state changes with a pipeline buffer. In Proceedings of the 9th International Fall Workshop Vision, Modeling, and Visualization (VMV), pages 217--224, 2004.
• 14: Harald Räcke , Christian Sohler , Matthias Westermann, Online Scheduling for Sorting Buffers, Proceedings of the 10th Annual European Symposium on Algorithms, p.820-832, September 17-21, 2002
• 15: Toby J. Teorey , Tad B. Pinkerton, A comparative analysis of disk scheduling policies, Communications of the ACM, v.15 n.3, p.177-184, March 1972 [doi>10.1145/361268.361278]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory

Keywords:
general metric spaces, online algorithms, reordering buffer, sorting buffer