Course Details for A.Y. 2011/2012

Course Objectives

Knowledge of advanced algorithmic techniques; ability to individuate, formalize and solve optimization problems; concept of approximation; ability to classify problems according to their degree of approximability; ability to collaborate for the realization of applicative projects in group.

Course Content

• Review of computational complexity and intractability. Optimization problems. Approximation algorithms.
• Algorithmic techniques: greedy.
• Algorithmic techniques: local search and dynamic programming.
• Linear programming techniques: rounding and primal-dual methods
• Polynomial Time Approximation Schemes (PTAS) and Fully Polynomial Time Approximation Schemes (FPTAS).
• Negative approximation results and gap technique. Complexity classes for optimization problems and their inclusions

Prerequisites and Learning Activities

KNOWLEDGE: fundamentals of programming, discrete mathematics, algorithms and data structures, computer architectures, reading and understanding of the English language SKILLS: ability to integrate classroom and homework study, ability to interact with the teacher during the class for originating discussion.

Textbooks

• Vijay V. Vazirani, Approximation Algorithms , Springer. 2001. ISBN: 3-540-65367-8    
• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation , Springer. 1999. ISBN: 3-540-65431-3    

Internet Resources

Course page updates

• A.Y. 2010/2011
• A.Y. 2011/2012
• A.Y. 2012/2013
• A.Y. 2013/2014
• A.Y. 2014/2015
• A.Y. 2015/2016
• A.Y. 2016/2017
• A.Y. 2017/2018
• A.Y. 2018/2019
• A.Y. 2019/2020