[MAC499] Algoritmos de aproximação

[Cristina Gomes Fernandes <cris@ime.usp.br>]

Alô, 

Eu tenho um projetinho para quem se interessar. O projeto trata-se da
implementação e comparação de alguns algoritmos para um problema em
grafos.

O problema é o problema de Steiner: dado um grafo G com custos nas
arestas e um conjunto R de vértices, encontrar uma árvore de custo
mínimo que contenha os vértices de R. Esse problema tem aplicações no
projeto de redes e coisas do gênero.

O problema é difícil, mas existem vários algoritmos de aproximação
para ele (algoritmos que produzem soluções que garantidamente não
estão muito longe da mínima; mas você não precisa saber disso para
fazer o trabalho).

Os algoritmos que eu gostaria de ver implementados aparecem em
pseudo-código na dissertação do Eduardo Gondo, um aluno de mestrado
meu, e são mais ou menos fáceis de implementar. Envolvem coisas do
tipo encontrar caminho mínimo entre dois vértices, encontrar uma
árvore geradora mínima e uma busca exaustiva de árvores pequenas de um
certo tipo. 

Se você quiser, pode dar uma espiada nos algoritmos na dissertação 
do Eduardo em

http://www.ime.usp.br/~cris/gondo.ps.gz

O projeto consistiria da implementação de alguns dos algoritmos que
aparecem na dissertação dele (eles são todos meio parecidos, então
possivelmente daria para implementar facilmente uns três deles pelo
menos) e da execução de alguns testes com instâncias aleatória, para
compararmos a performance dos algoritmos (ou seja, qual deles produzem
as árvores de custo menor? Qual é a razão obtida na prática por estes
algoritmos? Etc.)

Se alguém estiver interessado nesse trabalho, pode me escrever ou 
aparecer na minha sala (150-B), ou me escrever para marcarmos um 
horário para conversar. 

Até, 

Cris