A deterministicO(k 3)-competitivek-server algorithm for the circle

Suppose thatk mobile servers are located on a circle. Repeatedly, a request at a pointx on the circle appears. To serve this request one of the servers has to be moved tox. The cost of moving a server tox is the distance on the circle between the server's previous location andx. The decision which server to move has to be doneon-line; that is, without the knowledge of future requests. We give a deterministic on-line algorithm for making these decisions. Our algorithm isO(k ³)-competitive: for any sequence of requests, the cost incurred by our algorithm in serving this sequence is bounded (up to an additive constant) byO(k ³) times the cost of serving this sequence using the bestoff-line algorithm; i.e., an algorithm that hasa priori knowledge of the whole sequence. Our algorithm is the best deterministic constructive algorithm fork>2.