Defesa de Dissertação de Mestrado: André Willik Valenti
Document Actions
Defesa de Dissertação de Mestrado: Mário César San Felice
O Problema do k-Servidor.
| What | Defesa de Mestrado |
|---|---|
| When |
22/03/2010 from 14:00 to 16:00 |
| Where | Auditório do IC - Sala 85 - IC 2 |
| Add event to calendar |
vCal
iCal
|
Nesta dissertação consideramos o problema do k-Servidor. Neste problema temos k servidores em um espaço métrico e nosso objetivo é atender a uma sequência de requisições, de modo a minimizar a distância total percorrida pelos servidores. Dedicamos especial atenção à conjectura do k-Servidor: qualquer espaço métrico admite um algoritmo k-competitivo para o problema do k-Servidor. Este é um dos problemas mais importantes em aberto da área de computação online.
O algoritmo da função trabalho, proposto por Chrobak e Larmore, é especialmente relevante para a conjectura. Isto porque foi provado que este algoritmo é k-competitivo para diversos casos particulares do problema do k-Servidor. Além disso, acredita-se que este algoritmo é de fato k-competitivo para todo espaço métrico. Por isto, o entendimento deste algoritmo é 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 é (2k-1)-competitivo para todo espaço métrico. Este é o resultado mais importante relacionado ao problema do k-Servidor. Além disso, mostramos que a conjectura do k-Servidor vale para alguns casos particulares do problema.
Resultado do Processo Seletivo de Aluno Regular para a Pós-Graduação do IC no 1s2012.
