Finding the shortest path on-line

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.

back to TU/e Combinatorial Theory Seminar announcements