Algoritmos de aproximação primal-dual e suas implementações ----------------------------------------------------------- Aluno: Rafael Pereira Luna Neste trabalho, planejamos fazer um estudo de algoritmos de aproximação primal-dual. Após estudar rapidamente os conceitos e idéias básicas utilizadas no projeto de algoritmos de aproximação, nos concentraremos em algoritmos de aproximação primal-dual. A base de um algoritmo de aproximação primal-dual é um processo de clustering de Goemans e Williamson. Existem várias maneiras de se implementar tal processo. Planejamos estudar a implementação básica do processo de clustering e uma implementação mais eficiente e mais simples, que tem uma pequena perda na qualidade da solução - a implementação proposta por Cole et al. [2]. O estudo das duas implementações será feito em cima de um problema concreto: o problema da floresta de Steiner [1]{seção 5.4}. Além do estudo teórico, pretendemos implementar as duas versões do algoritmo para o problema da floresta de Steiner: com o processo de clustering implementado de forma básica e a implementação de Cole et al. Se houver tempo, estudaremos ainda a implementação de Gabow, Goemans e Williamson [3] do processo de clustering, que é mais rápida que a básica e não implica em nenhuma perda de qualidade. Cronograma tarefa maio junho julho agosto setembro outubro novembro 1 x 2 x x 3 x x 4 x x x 5 x x Tarefas: 1. estudo inicial de algoritmos de aproximação (partes dos cap 1, 2, 3 e 4). 2. algoritmos de aproximação primal-dual (cap 5). 3. implementação básica do algoritmo para floresta de Steiner. 4. implementação de Cole et al []. 5. escrita do trabalho. Referências [1] M.H. Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. Miyazawa, J.C. Pina Jr., J. Soares, Y. Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, Publicações Matemáticas do IMPA, 2001. [2] R. Cole, R. Hariharan, M. Lewenstein e E. Porat, A Faster Implementation of the Goemans-Williamson Clustering Algorithm, SODA 2001. [3] H. Gabow, M. Goemans e D. Williamson, An Efficient Approximation Algorithm for the Survivable Network Design Problem, IPCO 1993.