MACapro Algoritmos de Aproximação

OBSERVAÇÃO:  Esta disciplina será oferecida no primeiro semestre de 2003 sob a sigla "de aluguel" MAC0423, que pertence à disciplina Introdução à Teoria da Computabilidade (que trata de assunto completamente diferente...).

OBJETIVOS: Familiarizar os alunos com as técnicas de desenvolvimento e análise de algoritmos de aproximação para problemas combinatórios e com os resultados da teoria de complexidade relacionados a aproximações. São estudados algoritmos de aproximação para vários problemas, dentre os quais destacamos problemas de escalonamento, bin packing, geometria computacional e otimização sobre grafos.

PROGRAMA: 1. Recapitulação de resultados básicos sobre grafos, complexidade computacional e probabilidade. 2. Métodos de desenvolvimento de algoritmos de aproximação: métodos métricos, métodos probabilísticos, métodos baseados em programação semidefinida e métodos primais-duais. 3. Algoritmos de aproximação para problemas de escalonamento, bin packing, geometria computacional, e otimização sobre grafos (coberturas, empacotamentos, conectividade e cortes). 4. Complexidade de aproximações: classes de complexidade Max SNP e APX, reduções, alguns resultados negativos de aproximação.

PRÉ-REQUISITOS: MAC0338 e MAC0315.

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.

BIBLIOGRAFIA:

• D. Hochbaum (ed.), Approximation Algorithms for NP-hard Problems, PWS Publishing Company, 1997.
• V. Vazirani, Approximation Algorithms, Springer, 2001.
• M.H. de Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. Miyazawa, J.C. de Pina Jr., J.A.R. Soares, Y. Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, Publicações Matemáticas do IMPA, 2001.
• E.W. Mayr, H.J. Prömel, A. Steger, Lectures on Proof Verification and Approximation Algorithms, Springer, 1998.