A deterministic O(k3)-competitive k-server algorithm for the circle
Abstract
Suppose that k mobile servers are located on a circle. Repeatedly, a request at a point x on the circle appears. To serve this request one of the servers has to be moved to x. The cost of moving a server to x is the distance on the circle between the server's previous location and x. The decision which server to move has to be done on-line; that is, without the knowledge of future requests. We give a deterministic on-line algorithm for making these decisions. Our algorithm is O(k3)-competitive: for any sequence of requests, the cost incurred by our algorithm in serving this sequence is bounded (up to an additive constant) by O(k3) times the cost of serving this sequence using the best off-line algorithm; i.e., an algorithm that has a priori knowledge of the whole sequence. Our algorithm is the best deterministic constructive algorithm for k>2. © 1994 Springer-Verlag New York Inc.