Estudo experimental de aproximações para o problema de Steiner -------------------------------------------------------------- Aluno: Michel Vale Ferreira Neste trabalho, planejamos implementar de três a quatro algoritmos de aproximação para o problema de Steiner em grafos e fazer um estudo comparativo da sua performance em instâncias aleatórias e em instâncias das bibliotecas encontradas em http://ganley.org/steiner/related.html. Os algoritmos que pretendemos implementar aparecem descritos em pseudocódigo na dissertação de Gondo [1]. São eles o algoritmo de Zelikovsky (cap 2), o algoritmo do ganho relativo (cap 4), o algoritmo de Robin e Zelikovsky (cap 6) e, se houver tempo, o algoritmo do pré-processamento, de Karpinsky e Zelikovsky (cap 5). Esses algoritmos não são muito complicados. Eles são variantes uns dos outros e usam várias rotinas em comum, assim nos parece viável implementar vários deles e compará-los experimentalmente no período de tempo disponível. Será interessante observar o comportamento destes algoritmos na prática frente ao que dizem suas análises teóricas. Cronograma ---------- (a) (b) (c) (d) (e) (f) (g) tarefa maio junho julho agosto setembro outubro novembro 1 x 2 x x x x 3 x x x 4 x x Tarefas: 1. estudo dos conceitos básicos. 2. implementação dos algoritmos. 3. testes e comparações dos algoritmos. 4. escrita do trabalho. (a) Estudo da notação e do problema (cap 1) e implementação dos algoritmos de Dijkstra e Kruskal. (b) Estudo e implementação do algoritmo de Zelikovsky. (c) Estudo e implementação dos algoritmos do ganho relativo e de Robin e Zelikovsky. (d) Término das implementações e testes comparativos com instâncias aleatórias. (e) testes comparativos com instâncias da biblioteca http://ganley.org/steiner/related.html. (f) término dos estudos comparativos e início da escrita do trabalho. (g) finalização da escrita do trabalho. Referências [1] E.K. Gondo, Árvores k-Restritas e Aproximações para Árvores de Steiner, Dissertação de Mestrado, IME-USP 2002.