Informatica Teorica II

Materiale didattico

• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998.

• Capitolo 2: Design Techniques for Approximation Algorithms
• Capitolo 3: Approximation Classes
• Capitolo 4: Input-Dependent and Asymptotic Approximation
• Capitolo 5: Approximation through Randomization
• Bibliografia

• D. Bovet, P. Crescenzi, Introduction to the Theory of Complexity (reso disponibile nel pubblico dominio dagli autori)

• C.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
• V.V. Vazirani, Approximation Algorithms, Springer, 2004.