Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275810
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: O problema do k-Servidor
Title Alternative: The k-server problem
Author: San Felice, Mário César, 1985-
Advisor: Lee, Orlando, 1969-
Abstract: Resumo: Nesta dissertação consideramos o problema do k-Servidor. Neste problema temos k servidores em um espaço métrico e nosso objetivo e atender a uma seqüência de requisições, de modo a minimizar a distancia total percorrida pelos servidores. Dedicamos especial atenção a conjectura do k-Servidor: qualquer espaço métrico admite um algoritmo k-competitivo para o problema do k-Servidor. Este e um dos problemas mais importantes em aberto da area de computação online. O algoritmo da função trabalho, proposto por Chrobak e Larmore, e especialmente relevante para a conjectura. Isto porque foi provado que este algoritmo e k-competitivo para diversos casos particulares do problema do k-Servidor. Alem disso, acredita-se que este algoritmo e de fato k-competitivo para todo espaço métrico. Por isto, o entendimento deste algoritmo e central neste trabalho. Para analisar o algoritmo da função trabalho são utilizados diversos resultados auxiliares desenvolvidos por vários autores. Neste trabalho tentamos apresentar de forma coesa uma coletânea destes resultados. A partir desta mostramos uma prova do teorema de Koutsoupias e Papadimitriou: o algoritmo da função trabalho e (2k - 1)-competitivo para todo espaço métrico. Este e o resultado mais importante relacionado ao problema do k-Servidor. Alem disso, mostramos que a conjectura do k-Servidor vale para alguns casos particulares do problema

Abstract: 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
Subject: Problema do k-servidor
Algoritmos de computador
Otimização combinatória
Complexidade computacional
Language: Português
Editor: [s.n.]
Date Issue: 2010
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
SanFelice_MarioCesar_M.pdf1.56 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.