MAC 5727 - Critério de avaliação

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

Datas prováveis de prova:

• P1: 7 de abril (ou mais tarde).
• P2: ?? de junho.

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. 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.
• E.W. Mayr, H.J. Prömel, and A. Steger (eds.), Lectures on Proof Verification and Approximation Algorithms, Springer, 1998.
• 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).