Theory of Computing
-------------------
Title     : Reordering Buffers for General Metric Spaces
Authors   : Matthias Englert, Harald Raecke, and Matthias Westermann
Volume    : 6
Number    : 2
Pages     : 27-46
URL       : https://theoryofcomputing.org/articles/v006a002

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.  When serving a request the cost is equal to
the distance, in the metric space, between this request and the
previously served request.  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 where the goal is to minimize the total cost. 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 weighted trees whose competitive ratio depends on  k  and the
hop-diameter of the tree.   Then we show how to improve this 
competitive ratio to  O(log^2 k)  for metric spaces that correspond 
to hierarchically well-separated trees. Combining this result with 
the results on the probabilistic approximation of arbitrary metrics 
by tree metrics due to Fakcharoenphol, Rao, and Talwar, we obtain a 
randomized strategy for general metric spaces that achieves a 
competitive ratio of  O((log^2 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.