A Randomized Algorithm for Two Servers on the Line

In the k -server problem we wish to minimize, in an online fashion, the movement cost of k servers in response to a sequence of requests. For two servers, it is known that the optimal deterministic algorithm has competitive ratio 2, and it has been a long-standing open problem whether it is possible to improve this ratio using randomization. We give a positive answer to this problem when the underlying metric space is a real line, by providing a randomized online algorithm for this case with competitive ratio at most 155 78 ≈1.987. This is the first algorithm for two servers that achieves a competitive ratio smaller than 2 in a nonuniform metric space with more than three points. We consider a more general problem called the ( k , l )- server problem , in which a request is served using l out of k available servers. We show that the randomized 2-server problem can be reduced to the deterministic (2 l , l )-server problem. We prove a lower bound of 2 on the competitive ratio of the (4, 2)-server problem. This implies that one unbiased random bit is not sufficient to improve the ratio of 2 for the two-server problem. Then we give a 155 78 -competitive algorithm for the (6, 3)-server problem on the real line. Our algorithm is simple and memoryless. The solution has been obtained using linear programming techniques that may have applications for other online problems.