MAC0450  Algoritmos de Aproximação

Por | Em

OBJETIVOS:  Familiarizar os alunos com técnicas de projeto e análise de algoritmos de aproximação e com os resultados de inaproximabilidade. Estudar algoritmos de aproximação para vários problemas, dentre os quais destacamos problemas de escalonamento, bin packing, projeto de redes e otimização em grafos.

Familiarize students with design and analysis of approximation algorithms, and with inapproximability results. Study approximation algorithms for several problems, such as scheduling, bib packing, network design, and optimization in graphs.

PROGRAMA RESUMIDO:  Técnicas de projeto e análise de algoritmos de aproximação e resultados de inaproximabilidade.

Techniques of design and analysis of approximation algoritms, and inapproximability results.

PROGRAMA:  Recapitulação de resultados básicos sobre grafos, complexidade computacional e probabilidade. Métodos de projeto de algoritmos de aproximação: métricos, de arredondamento, probabilísticos, baseados em programação linear e semidefinida, primais-duais. Algoritmos de aproximação para problemas de escalonamento, bin packing, projeto de redes e otimização em grafos. Complexidade computacional: classes de complexidade Max SNP e APX, reduções, alguns resultados inaproximabilidade.

Review of basic results in graphs, computational complexity, and probability. Methods of design of approximation algorithms: metric, probabilistic, linear and semidefinite programming, primal-dual. Approximation algorithms for scheduling, bib packing, network design, and optimization in graphs. Computational complexity: Max SNP and APX classes, reductions, and inapproximability results.

RESPONSÁVEL: Cristina Gomes Fernandes, Yoshiko Wakabayashi.

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étodo: provas e exercícios.
Critério: média ponderada de provas e exercícios.
Norma de recuperação: média ponderada entre a nota final e a nota na prova de recuperação.

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.
  • D.P. Williamson, D.B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

OBSERVAÇÃO:  Disciplina optativa eletiva no currículo do BCC.

 

[Veja dados da disciplina no JúpiterWeb]

Oferecimentos recentes da disciplina: 2012/2 2009/1, 2000/1, 2003/1.