MAC0450 Algoritmos de Aproximação
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.
RESPONSÁVEL: Cristina Gomes Fernandes.
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 BÁSICA:
- 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.
OBSERVAÇÃO: Disciplina optativa eletiva no currículo do BCC.
[Veja dados da disciplina no JúpiterWeb]