MAC5727 / MAC0450 -- Algoritmos de Aproximação
2o. Semestre de 2018

1. Material básico

1. Livro-texto: Uma introdução sucinta a algoritmos aproximação (disponível em formato pdf e ps.gz)

2. Outros livros e notas de aula

1. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial approximation problems and their approximability properties
2. M. Goemans, Approximation algorithms, 1994. (notas de aula)
3. D. Hochbaum (ed.), Approximation Algorithms for NP-hard problems, PWS Publishing Company, 1997. (Disponível na Biblioteca do IME - BIME)
4. R. Motwani, Lectures Notes on Approximation Algorithms
5. V. Vazirani, Approximation Algorithms Informações sobre o livro (Disponível na BIME)
6. D.P Williamson and D. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011
7. D. Williamson, Lecture Notes on Approximation Algorithms, 1998
8. Combinatorial Optimization (eds. P. Crescenzi, V. Kann), A list of NP-complete optimization problems

3. Conhecimentos prévios necessários e/ou bem-vindos (suprir se necessário)

1. Programação Linear
   • V. Chvátal, Linear Programming, W.H. Freeman, N. York, 1983. (Disponível na BIME)
2. Teoria dos Grafos
   • J.A. Bondy and U.S.R. Murty, Graph Theory, (Graduate Texts in Mathematics, Volume 244) Springer, 2008 . Tem versão online - veja aqui
   • R. Diestel, Graph Theory, (Graduate Texts in Mathematics, Volume 173) Springer, Heidelberg. (Disponível na BIME) [veja aqui versão online]
3. Skiena's Algorithms Lectures (video, audio, slides)
4. Problemas em P, em NP e a questão "P versus NP"

4. Outros textos recomendados (para melhorar a formação)

1. Como escrever "provas matemáticas" (1a. edição disponível na BIME)
2. Como escrever textos matemáticos(Handbook of Writing for the Mathematical Sciences (N.J. Higham) | Mathematical Writing (Knuth, Larrabee, Roberts) | How to write Mathematics (Steenrod, Halmos, Schiffer, Dieudonné)

3. Nova ortografia da língua portuguesa
   • Guia Prático da Nova Ortografia (em pdf) e-book gratuito (distribuído pela Michaelis - editora Melhoramentos) --- obtido aqui