Aluno: Edênis Freindorfer Azevedo
Orientador: Cristina Gomes Fernandes
Tema:Método Primal-Dual para o Problema de Steiner com Coleta de Prêmios

Motivação:

Com o surgimento do campo da otimização discreta, houve o interesse pela resolução de problemas desta classe que são NP-difíceis. Mas, a menos que P = NP, não existem algoritmos que resolvam em tempo polinomial com relação ao tamanho da entrada. Portanto, investigar pela busca de boas soluções em tempo polinomial, mesmo que não sejam ótimas, é uma possível saída para tantos destes problemas NP-completos que aparecem não somente em modelos matemáticos avançados como na vida real.

Em particular, o Problema de Steiner com Coleta de Prêmios é importante para o design e layout de redes de telecomunicações. Mas, mais importante que isso, é necessário mostrar que o algoritmo projetado pode ser implementado em uma linguagem de programação e ter tempo de execução polinomial.

Objetivo do trabalho:

O objetivo deste trabalho é o estudo de implementações de algoritmos de aproximação baseados no método primal-dual. Especificamente pretendemos implementar, de maneira tão eficiente quanto possível, um conhecido e sofisticado algoritmo de aproximação primal-dual para o Problema de Steiner com Coleta de Prêmios.

Atividades já realizadas:

Estudamos o que eram algoritmos de aproximação, seus tipos, como faziam para se aproximar de uma solução ótima do problema e como analisar sua razão de aproximação. Em particular, estudamos as possíveis maneiras de atacar um problema NP-difícil qualquer, como por exemplo o problema da Cobertura por Conjuntos, e vimos quais técnicas eram aplicáveis, que transformações eram feitas na apresentação do problema (usando programação linear inteira) para sua resolução e para análise da razão de aproximação de cada algoritmo.
Para compreender um pouco mais sobre a implementação de um algoritmo primal-dual e para treinar o que será feito com o problema de Steiner com Coleta de Prêmios , estudamos e implementamos um algoritmo em C para o problema do Feedback Vertex Set, o que será descrito e explicado mais detalhadamente na seção 2 do arquivo abaixo.

Cronograma de Atividades simplificado(legenda em baixo):
Atividades MAIO JUN JUL AGO SET OUT NOV
1 X - - - - - -
2 X - - - - - -
3 X X - - - - -
4 - X X - - - -
5 - - X - - - -
6 - - X X - - -
7 - - - X X X -
8 - - - - X X X
9 - - - - - X -
1-Término da redação do capítulo sobre o Feedback Vertex Set;
2-Revisão do estudo do algoritmo primal-dual para o Generalized Steiner Problem;
3-Implementação do algoritmo para o Generalized Steiner Problem;
4-Redação do capítulo do algoritmo primal-dual do Generalized Steiner Problem;
5-Revisão do primal-dual para o Prize Collecting Steiner Problem;
6-Implementação do algoritmo para o Prize Collecting Steiner Problem;
7-Redação do capítulo sobre o Prize Collecting Steiner Problem;
8- Finalização do TCC; e
9- Preparação do pôster e da apresentação do TCC.