PERIODO: GENNAIO 2016

Il Corso si propone di fornire le conoscenze di base sulla complessita’ computazionale e sugli algoritmi di approssimazione polinomiale per problemi di ottimizzazione combinatoria.Si esporrranno i concetti di base di complessita’ computazionale e verranno introdotti i principali schemi di approssimazione polinomiale. Verranno dati esempi di algoritmi approssimati per problemi paradimatici di teoria dei grafi ed ottimizzazione combinatoria.

Aim of the course is to provide an introduction to computational complexity and approximation for combinatorial optimization problems. Basics on computational complexity polynomial time approximation schemes will be presented with examples of approximation algorithms for paradigmatic graph theory and combinatorial optimization problems.

Complessità computazionale:
• Algoritmi polinomiali
• Classi di complessità P e NP
• NP-completezza in senso forte ed in senso debole
• Riduzioni polinomiali

Approssimazione:
• Approssimazione polinomiale
• PTAS e FPTAS
• Inapprossimabilità



Computational complexity:
• polynomial time algorithms
• P and NP complexity classes
• Strong and Weak NP-completeness
• Polynomial time reductions

Approximation:
• Polynomial time approximation
• PTAS and FPTAS
• Inapproximability


Timetable

Location: Classroom C (close to classroom 14 in the main building of Politecnico)

Dates:
January 7 9-12
January 19 10-13
January 22 14-17
January 26 9-12
January 29 9-12