O problema do k-Servidor / The k-server problem
AUTOR(ES)
Mário César San Felice
DATA DE PUBLICAÇÃO
2010
RESUMO
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
ASSUNTO(S)
otimização combinatória problema do k-servidor algoritmos de computador complexidade computacional k-server problem computer algorithms combinatorial optimization computational complexity
