Algoritmos de Aproximação

Curso ministrado no DCC da UFMS

Segundo semestre de 2001

• Uma introdução [ps | pdf]
• Ementa da disciplina

• Critério de avaliação e bibliografia

• Lista de discussão

• Programação das aulas

• Listas de exercícios

• Lista de alunos e notas

• Previsão das próximas aulas:
  • Outubro: dias 22 (uma aula de manhã) e 23 (prova de manhã e uma aula à tarde).
  • Novembro: dias 12, 13 e 14.
  • Dezembro: dias 1, 3 e 4.

Bibliografia

• 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, J. Soares e Y. Wabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, livro do Colóquio Brasileiro de Matemática, 2001.
• M. Goemans, Approximation algorithms, 1994. (notas de aula)
• M. Goemans, and D. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfability Problems using Semidefinite Programming, JACM, 42:1115-1145, 1995.
• D. Hochbaum (ed.), Approximation Algorithms for NP-hard problems, PWS Publishing Company, 1997.
• Y. Kohayakawa, and J.A. Soares, Demonstrações Transparentes e a Impossibilidade de Aproximações, XX Colóquio Brasileiro de Matemática, IMPA, 1995.
• R. Motwani, Lecture Notes on Approximation Algorithms, book in preparation.
• V. Vazirani, Approximation Algorithms, preprint, 1999.
• D. Williamson, Lecture Notes on Approximation Algorithms, Fall 1998.

Alguns links relacionados com tópicos do curso

• Approximation Algorithms for NP-Hard Problems
• A Compendium of NP Optimization Problems
• Michael Goemans
• Rajeev Motwani
• Vijay Vazirani
• David Williamson