Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275810
Full metadata record
DC FieldValueLanguage
dc.contributor.CRUESPUNIVERSIDADE ESTADUAL DE CAMPINASpt_BR
dc.descriptionOrientador: Orlando Leept_BR
dc.descriptionDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computaçãopt_BR
dc.format.extent85 f. : il.pt_BR
dc.format.mimetypeapplication/octet-streampt_BR
dc.languagePortuguêspt_BR
dc.typeDISSERTAÇÃOpt_BR
dc.titleO problema do k-Servidorpt_BR
dc.title.alternativeThe k-server problempt_BR
dc.contributor.authorSan Felice, Mário César, 1985-pt_BR
dc.contributor.advisorLee, Orlando, 1969-pt_BR
dc.contributor.institutionUniversidade Estadual de Campinas. Instituto de Computaçãopt_BR
dc.contributor.nameofprogramPrograma de Pós-Graduação em Ciência da Computaçãopt_BR
dc.subjectProblema do k-servidorpt_BR
dc.subjectAlgoritmos de computadorpt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subjectComplexidade computacionalpt_BR
dc.subject.otherlanguageK-server problemen
dc.subject.otherlanguageComputer algorithmsen
dc.subject.otherlanguageCombinatorial optimizationen
dc.subject.otherlanguageComputational complexityen
dc.description.abstractResumo: 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 problemapt
dc.description.abstractAbstract: 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 casesen
dc.publisher[s.n.]pt_BR
dc.date.issued2010pt_BR
dc.identifier.citationSAN FELICE, Mário César. O problema do k-Servidor. 2010. 85 f. Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/275810>. Acesso em: 16 ago. 2018.pt_BR
dc.description.degreelevelMestradopt_BR
dc.description.degreedisciplineOtimização Combinatoriapt_BR
dc.description.degreenameMestre em Ciência da Computaçãopt_BR
dc.contributor.committeepersonalnameFernandes, Cristina Gomespt_BR
dc.contributor.committeepersonalnameMeira, Luis Augusto Angelottipt_BR
dc.contributor.committeepersonalnameMiyazawa, Flávio Keidipt_BR
dc.date.available2018-08-16T05:20:45Z-
dc.date.accessioned2018-08-16T05:20:45Z-
dc.description.provenanceMade available in DSpace on 2018-08-16T05:20:45Z (GMT). No. of bitstreams: 1 SanFelice_MarioCesar_M.pdf: 1592906 bytes, checksum: 7d6d43104cbdeb2ad46a93e6ef11ae23 (MD5) Previous issue date: 2010en
dc.identifier.urihttp://repositorio.unicamp.br/jspui/handle/REPOSIP/275810-
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.