Livros
-
M.H. de Carvalho,
M.R. Cerioli,
R. Dahab,
P. Feofiloff,
C.G. Fernandes,
C.E. Ferreira,
K.S. Guimarães,
F.K. Miyazawa,
J.C. de Pina Jr.,
J.A.R. Soares,
Y. Wakabayashi,
Uma Introdução Sucinta a Algoritmos de Aproximação,
XXIII Colóquio Brasileiro de Matemática,
Publicações Matemáticas do IMPA, 2001.
[Cópia pdf do livro e errata.]
Vamos nos referir a esse livro como
o Aprox
. -
David Williamson,
David Shmoys,
The Design of Approximation Algorithms.
2009.
- D. Hochbaum (ed.),
Approximation Algorithms for NP-hard Problems,
PWS Publishing Company, 1997.
- Vijay Vazirani,
Approximation Algorithms,
Springer, 2001.
-
Rajeev Motwani,
Prabhakar Raghavan,
Randomized Algorithms,
Cambridge University Press, 1995.
- G. Ausiello,
P. Crescenzi,
G. Gambosi,
V. Kann,
A. Marchetti-Spaccamela,
M. Protasi,
Complexity and Approximation,
Springer, 1999.
- E.W. Mayr, H.J. Prömel, A. Steger,
Lectures on Proof Verification and Approximation Algorithms,
Lecture Notes in Computer Science 1367,
Springer, 1998.
- Y. Kohayakawa, J.A. Soares,
Demonstrações Transparentes e
a Impossibilidade de Aproximações,
XX Colóquio Brasileiro de Matemática, IMPA, 1995.
-
E. Boros, P.L. Hammer (eds.), Discrete Optimization - The State of the Art, Topics in Discrete Mathematics v.11, a reprint of Discrete Applied Mathematics 123/1-3. ISBN: 0-444-51295-0
Notas de aula
- Michael Goemans,
Approximation Algorithms,
1994, notas de aula
-
David P. Williamson,
Lecture Notes on Approximation Algorithms,
Fall 1998
-
Rajeev Motwani,
Lecture Notes on Approximation Algorithms,
book in preparation, 1999.
- J. Cheriyan, R. Ravi, Lecture Notes on Approximation Algorithms for Network Problems
Assuntos relacionados
- V. Chvátal,
Linear programming,
W.H. Freeman, 1983.
- P. Feofiloff,
Algoritmos de Programação Linear,
1999.
-
T.H. Cormen,
C.E. Leiserson,
R.L. Rivest,
C. Stein,
Introduction to Algorithms, 2nd. edition,
MIT Press e McGraw-Hill, 2001.
[Há uma versão em português, mas a tradução e a tipografia não são boas.] - C.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
Manuais de complexidade
-
M.R. Garey, D.S. Johnson,
Computers and Intractability:
A Guide to the Theory of NP-completeness,
Freeman, 1979.
- Pierluigi Crescenzi, Viggo Kann (eds.),
A Compendium of NP Optimization Problems,
www.csc.kth.se/~viggo/problemlist/
- Lane A. Hemaspaandra, Leen Torenvliet, Theory of Semi-Feasible Algorithms, Springer-Verlag, 2003.