A COMPETITIVE 2-SERVER ALGORITHM

The K-server problem is the problem of planning the motion of K mobile servers in a metric space. We give an on-line algorithm for the 2-server problem in any metric space. The total cost of this algorithm on any sequence of requests is bounded by ten times the cost of the optimal off-line algorithm on that sequence. The rule is a modified version of the balance algorithm; it sends the server that minimizes the quantity: (total distance traversed so far by that server + twice the distance of that server to the next request). This is the first provable competitive rule that can be evaluated in a constant number of arithmetic operations per request with only one variable. This contrasts with the 2-competitive 2-server algorithm in [5] which requires maintaining O(t) memory locations and O(t) time to decide which server to send, where t is the minimum of the number of points in the metric space and the number of requests. Our rule naturally generalizes to more than two servers, and we conjecture that it is also competitive in this case.