Università Roma Tre

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.

[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