TY - GEN
T1 - Reordering buffers for general metric spaces
AU - Englert, Matthias
AU - Räcke, Harald
AU - Westermann, Matthias
PY - 2007
Y1 - 2007
N2 - 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(log2 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(log2 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.
AB - 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(log2 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(log2 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.
KW - General metric spaces
KW - Online algorithms
KW - Reordering buffer
KW - Sorting buffer
UR - http://www.scopus.com/inward/record.url?scp=35448997323&partnerID=8YFLogxK
U2 - 10.1145/1250790.1250871
DO - 10.1145/1250790.1250871
M3 - Conference contribution
AN - SCOPUS:35448997323
SN - 1595936319
SN - 9781595936318
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 556
EP - 564
BT - STOC'07
T2 - STOC'07: 39th Annual ACM Symposium on Theory of Computing
Y2 - 11 June 2007 through 13 June 2007
ER -