Proposta de Trabalho de Conclus�o de Curso - 2009

Tema: M�todo dual-fitting.
Orientadora: Cristina Gomes Fernandes
Aluno: Leonardo Marchetti

Resumo da monografia a ser desenvolvida

   Neste trabalho iremos descrever um m�todo para analisar algoritmos de aproxima��o para problemas de otimiza��o chamado dual-fitting e apresentar algumas aplica��es dessa t�cnica.

   O m�todo em quest�o tem respaldo na teoria de dualidade em programa��o linear. Ele consiste em considerar um programa linear P que � uma relaxa��o do problema original para uma dada inst�ncia e seu programa linear dual D, e ent�o olhar para a solu��o devolvida pelo algoritmo para o problema original, que � tamb�m solu��o de P, e para alguma solu��o dual de D convenientemente associada ao algoritmo e ent�o, demonstrando mais alguns fatos e utilizando o valor �timo do dual como um limitante do problema original concluir que o algoritmo � uma c-aproxima��o para o problema original para alguma constante c.

   Mais informa��es relevantes ao conte�do da monografia se encontram nas outas se��es da proposta e no link em Atividades j� realizadas.

Objetivos do trabalho

   O nosso objetivo � escrever uma monografia sobre o m�todo dual-fitting, que contenha n�o s� a apresenta��o detalhada do m�todo como a sua aplica��o na an�lise de alguns algoritmos para alguns problemas conhecidos.

   Se poss�vel analisaremos algum algoritmo da literatura para o qual o m�todo dual-fitting n�o tenha sido usado em nenhuma an�lise, mas para o qual possamos aplicar o m�todo.

Atividades j� realizadas

   Algumas atividades v�m sendo realizadas desde abril de 2008.

   O estudo iniciou-se pelo aprendizado do m�todo dual-fitting que se deu principalmente atrav�s da leitura do Cap�tulo 13 do livro de Vazirani[1] e do que foi aprendido em aula na mat�ria optativa eletiva Algoritmos de Aproxima��o. Sobre o m�todo foi escrita uma explica��o detalhada que ser� utilizada como parte importante da monografia.

   Estudamos tamb�m uma aplica��o do m�todo para o problema da cobertura m�nima por conjuntos, baseando-se novamente no livro de Vazirani[1]. Mais uma se��o da monografia foi escrita sobre esse assunto.

   Fizemos um levantamento bibliogr�fico apenas inicial do assunto da monografia, onde encontramos mais tr�s artigos que falam do m�todo dual-fitting, um deles[2] j� foi escolhido para ser estudado no futuro.

Cronograma de atividades para o segundo semestre

   Durante o m�s de junho estudaremos o segundo exemplo apresentado no livro de Vazirani[1], que trata de uma variante do problema da cobertura m�nima por conjuntos.

   A seguir, passaremos a estudar o artigo de Athanassapoulos, Caragiannis e Kaklamanis[2], que trata ainda de outra variante do problema da cobertura m�nima por conjuntos.

   Aprofundaremos o levantamento bibliogr�fico e, dentre os resultados encontrados, escolheremos mais uma ou duas an�lises para apresentar nesta monografia.

   durante esse estudo tentaremos tamb�m encontrar um algoritmo da literatura para o qual o m�todo dual-fitting n�o tenha sido usado em nenhuma an�lise, mas para o qual possamos aplicar o m�todo.

   A monografia conter� tudo que for estudado no per�odo.

   Abaixo temos o cronograma em forma de tabela:

Atividade \ M�s JunhoJulho Agosto Setembro Outubro Novembro
Completar o estudo do cap�tulo 13 do livro de Vijay Vazirani [1]. *      
Estudar o artigo de Athanassopoulos, Caragiannis e Kaklamanis [2].  *    
Aprofundar o levantamento bibliogr�fico. **    
Selecionar o(s) pr�ximo(s) artigo(s) a ser(em) estudado(s). *    
Estudar mais uma ou duas aplica��es do m�todo.   **  
Prepara p�ster e a apresenta��o do trabalho.     * *
Revisar e entregar a monografia.       *

Estrutura esperada da monografia

   A monografia ser� composta por uma parte t�cnica e uma parte subjetiva.

   A parte t�cnica deve abordar os seguinte itens:

   A parte subjetiva deve abordar os seguintes itens:

Refer�ncias

   [1] V. V. Vazirani. Approximation Algorithms. Springer, 2001.
   [2] Stavros Athanassopoulos, Ioannis Caragiannis and Christos Kaklamanis. Analysis of Approximation Algorithms for k-Set Cover using
                  Factor-Revealing Linear Programs.
Theory of Computing Systems, to appear.