The Double Cover Algorithm (DC) for the k-server problem on the line. Mar 13 14:08 2002 Suppose that s_1, ... s_k are the positions of k servers on the line. Without loss of generality, s_i is to the left of s_i+1. If r is a request, move either one or two servers as follows: 1. If r = s_i, do nothing. 2. If r is to the left of s_1, move the leftmost server from s_1 to r. 3. If r is to the right of s_k, move the rightmost server from s_k to r. 4. If r is strictly between s_i and s_i+1 for some i, then move the two servers toward r at the same speed until one of them reaches r, at which time the other stops moving. Theorem: DC is k-competitive.