In this work we study the k-Server problem. In this problem, we have k
servers on a metric space that must attend a sequence of requests with
the goal of minimizing the total distance moved by the servers. We
dedicate special attention to the k-server conjecture: any metric
space allows for a k-competitive k-server algorithm. This is one of
the most important open problems in online computing.
The work function algorithm, proposed by Chrobak and Larmore, is very
relevant to the conjecture. It has been proved that this algorithm is
k-competitive for several special cases of the k-server problem.
Furthermore, most researchers believe that the algorithm is indeed
k-competitive for any metric space. Thus, a deeper understanding of
this algorithm plays a special role in this work.
To analyze the work function algorithm, we use many auxiliary results
developed by several authors. In this work we tried to present a
collection of these results in a concise way. From this, we present a
proof of Koutsoupias and Papadimitriou's theorem: the work function
algorithm is (2k-1)-competitive for any metric space. This is the
most important result related to the k-server problem. Moreover, we
show that the k-server conjecture holds in some special cases.