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).