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 2 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 ~ 1.987. This is the first algorithm for 2 servers that achieves a competitive ratio smaller than 2 in a non-uniform metric space with more than three points. In addition, the real-line case is of its own interest, since it can be seen as the problem of motion planning for 2-headed disks. 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.