René Sitters
|
A server, moving in a metric space, receives requests for service. A
single request consists of $k$ points in the metric space and it is
served by moving the server to one of the points. Each request must be
served before the next one is given and we assume the server has no
knowledge of future requests. The cost of the solution is the total
travelled distance, and the objective is minimizing the competitive ratio,
i.e. the ratio of the on-line cost and the optimal cost.
We show that the work function algorithm is O(k2k)-competitive. This result was given by W.R. Burley (J. of Algorithms 20, 1996). Burley's technique turns out to be useful for on-line server problems in general. |