PERIOD: MARCH Aim of the course is to provide an introduction to computational complexity and approximation for combinatorial optimization problems. Basics on computational complexity will be presented together with the main families of exact exponential algorithms and related worst-case complexity analysis. Polynomial time approximation schemes will be introduced with examples of approximation algorithms for paradigmatic graph theory problems and combinatorial optimization problems with emphasis on sequencing and scheduling problems. The course is taught in English.

• Computational complexity: • polynomial time algorithms • P and NP complexity classes • Strong and Weak NP-completeness • Polynomial time reductions • Exact exponential algorithms Approximation: • Polynomial time approximation • PTAS and FPTAS • Introduction to sequencing and scheduling • Three-field classification • Polynomially solvable machine scheduling problems • Constant approximation ratios in scheduling

le lezioni si terranno tutti in aula DIGEP B: 01/03/2018 09-12 08/03/2018 09-12 15/03/2018 09-12 22/03/2018 09-12 29/03/2018 09-12 05/04/2019 09-12 12/04/2019 09-11

Modalita di esame:

Exam:

...

Gli studenti e le studentesse con disabilita o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unita Special Needs, al fine di permettere al/la docente la declinazione piu idonea in riferimento alla specifica tipologia di esame.