The course aims at providing basic methodological and operative knowledge to represent and cope with decision processes and quantitative models.
Curriculum
teacher profile teaching materials
Computational Complexity: Decision vs. optimization problems. Classes P and NP. Polynomial reductions. NP-complete problems. Pseudo-polynomial algorithms.
Approximation algorithms: approximation classes (NPO, APX, PTAS, FPTAS, PO). Approximation algorithm for Vertex Cover: greedy, DFS, LP based algorithms (LP rounding and Primal Dual). 0-1 Knapsack problem: NP-completeness, DP algorithms, greedy algorithm, polynomial time approximation scheme, fully polynomial time approximation scheme.The travelling salesman problem, TSP: NP-completeness, non approximability result, study of real world applications, the metric TSP, approximation algorithms for the metric TSP, the TSPP. Scheduling on parallel machines: approximation algorithms.
Heuristic algorithms: constructive algortihms (for the TSP: inserition heuristics, geometric algorithms); local serach (for the TSP: 2-opt exchange, 3-opt, k-opt, OR-opt), variable depth method of local search (Lin-Kernigan algorithms), tabu search, simulated annealing, genetic algorithms.
Introduction to online algorithms.
[2] Lecture notes by prof. Agnetis (in italian: computational complexity, TSP, euristic algorithms).
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation,Combinatorial optimization problems and their approximability properties", Springer Verlag, 1999
[4] Slides of the lectures available on the web page of the course
Programme
Introduction to Combinatorial Optimization. Optimizations Algorithms. Computational complexity analysis of algorithms.Computational Complexity: Decision vs. optimization problems. Classes P and NP. Polynomial reductions. NP-complete problems. Pseudo-polynomial algorithms.
Approximation algorithms: approximation classes (NPO, APX, PTAS, FPTAS, PO). Approximation algorithm for Vertex Cover: greedy, DFS, LP based algorithms (LP rounding and Primal Dual). 0-1 Knapsack problem: NP-completeness, DP algorithms, greedy algorithm, polynomial time approximation scheme, fully polynomial time approximation scheme.The travelling salesman problem, TSP: NP-completeness, non approximability result, study of real world applications, the metric TSP, approximation algorithms for the metric TSP, the TSPP. Scheduling on parallel machines: approximation algorithms.
Heuristic algorithms: constructive algortihms (for the TSP: inserition heuristics, geometric algorithms); local serach (for the TSP: 2-opt exchange, 3-opt, k-opt, OR-opt), variable depth method of local search (Lin-Kernigan algorithms), tabu search, simulated annealing, genetic algorithms.
Introduction to online algorithms.
Core Documentation
[1] “Lecture Notes on Approximation Algorithms”, Volume I, R. Motwani.[2] Lecture notes by prof. Agnetis (in italian: computational complexity, TSP, euristic algorithms).
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation,Combinatorial optimization problems and their approximability properties", Springer Verlag, 1999
[4] Slides of the lectures available on the web page of the course
Type of delivery of the course
lectures, exercises, computer lab experienceType of evaluation
The exam is in two parts: the written exam (that usually lasts 2 hours) and the project evaluation. The written exam consists of a number of exercises (typically 4), aimed at veryfing the level of understanding of the theoretical concepts. The students' ability to apply the techniques explained in class is tested through the practical project. teacher profile teaching materials
Computational Complexity: Decision vs. optimization problems. Classes P and NP. Polynomial reductions. NP-complete problems. Pseudo-polynomial algorithms.
Approximation algorithms: approximation classes (NPO, APX, PTAS, FPTAS, PO). Approximation algorithm for Vertex Cover: greedy, DFS, LP based algorithms (LP rounding and Primal Dual). 0-1 Knapsack problem: NP-completeness, DP algorithms, greedy algorithm, polynomial time approximation scheme, fully polynomial time approximation scheme.The travelling salesman problem, TSP: NP-completeness, non approximability result, study of real world applications, the metric TSP, approximation algorithms for the metric TSP, the TSPP. Scheduling on parallel machines: approximation algorithms.
Heuristic algorithms: constructive algortihms (for the TSP: inserition heuristics, geometric algorithms); local serach (for the TSP: 2-opt exchange, 3-opt, k-opt, OR-opt), variable depth method of local search (Lin-Kernigan algorithms), tabu search, simulated annealing, genetic algorithms.
Introduction to online algorithms.
[2] Lecture notes by prof. Agnetis (in italian: computational complexity, TSP, euristic algorithms).
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation,Combinatorial optimization problems and their approximability properties", Springer Verlag, 1999
[4] Slides of the lectures available on the web page of the course
Programme
Introduction to Combinatorial Optimization. Optimizations Algorithms. Computational complexity analysis of algorithms.Computational Complexity: Decision vs. optimization problems. Classes P and NP. Polynomial reductions. NP-complete problems. Pseudo-polynomial algorithms.
Approximation algorithms: approximation classes (NPO, APX, PTAS, FPTAS, PO). Approximation algorithm for Vertex Cover: greedy, DFS, LP based algorithms (LP rounding and Primal Dual). 0-1 Knapsack problem: NP-completeness, DP algorithms, greedy algorithm, polynomial time approximation scheme, fully polynomial time approximation scheme.The travelling salesman problem, TSP: NP-completeness, non approximability result, study of real world applications, the metric TSP, approximation algorithms for the metric TSP, the TSPP. Scheduling on parallel machines: approximation algorithms.
Heuristic algorithms: constructive algortihms (for the TSP: inserition heuristics, geometric algorithms); local serach (for the TSP: 2-opt exchange, 3-opt, k-opt, OR-opt), variable depth method of local search (Lin-Kernigan algorithms), tabu search, simulated annealing, genetic algorithms.
Introduction to online algorithms.
Core Documentation
[1] “Lecture Notes on Approximation Algorithms”, Volume I, R. Motwani.[2] Lecture notes by prof. Agnetis (in italian: computational complexity, TSP, euristic algorithms).
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation,Combinatorial optimization problems and their approximability properties", Springer Verlag, 1999
[4] Slides of the lectures available on the web page of the course
Type of delivery of the course
lectures, exercises, computer lab experienceType of evaluation
The exam is in two parts: the written exam (that usually lasts 2 hours) and the project evaluation. The written exam consists of a number of exercises (typically 4), aimed at veryfing the level of understanding of the theoretical concepts. The students' ability to apply the techniques explained in class is tested through the practical project.