Monday

08.30-09.30 Course presentation - Audience contact
09.30-10.30 Complexity classes for decision problems
11.00-12.00 Optimization problems and their complexity
12.00-13.00 Algorithmic techniques for optimization problems
14.30-15.30 Randomized algorithms
15.30-16.30 The derandomization technique
17.00-18.0 Application to scheduling problems

Tuesday

08.30-09.30 Approximation algorithms: the class APX
09.30-10.30 Examples
11.00-12.00 Approximation algorithms based on linear programming
12.00-13.00 Examples
14.30-15.30 Mathematical programming based techniques
15.30-16.30 Semidefinite programming based techniques
17.00-18.00 Application to scheduling problems

Wednesday

08.30-09.30 First inapproximability results: the gap technique
09.30-10.30 Non-constant approximation algorithms
11.00-12.00 Polynomial-time approximation scheme
12.00-13.00 The class PTAS
14.30-15.30 Primal-dual based techniques
15.30-16.30 The metric spreading technique
17.00-18.00 Application to scheduling problems

Thursday

08.30-09.30 Fully polynomial-time approximation schemes
09.30-10.30 The class FPTAS
11.00-12.00 Advanced non-approximability results: the PCP theorem
12.00-13.00 Non-approximability of the maximum satisfiability problem
14.30-15.30 On-line algorithms ratio
17.00-18.00 Approximation on-line algorithms

Friday

08.30-09.30 Approximation preserving reducibility
09.30-10.30 Examples
11.00-12.00 The maximum clique problem
12.00-13.00 Conclusions and open problems
14.30-18.00 Free