About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica
Paper
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.