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.
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.
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.
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 | Junho | Julho | 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. | * |
A monografia ser� composta por uma parte t�cnica e uma parte subjetiva.
A parte t�cnica deve abordar os seguinte itens: