Critério de avaliação

Haverão duas provas e várias listas de exercícios.

A média das provas será a média arimética das notas de prova. A média das listas será a média arimética das notas das listas.

A média final levará em conta a sua média de prova, de listas e participação no curso em geral.

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.

Bibliografia básica de assuntos correlatos

• V. Chvátal, Linear programming, W.H. Freeman and Company, New York, 1983.
• T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press & McGraw-Hill, 1992.
• P. Feofiloff, Algoritmos de Programação Linear, 1999.
• M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freman, New York, 1979.
• C.H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, Massachusetts (1994).