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: