Coordinator: Prof. Antonio Vicino
Home |  DIISM |   | Login Privacy e Cookie policy



The Design And Analysis Of Algorithms For Combinatorial Optimization Problems


Gilles Schaeffer
Ecole Polytechnique Parigi
Course Type
Type B
June 5-9 2017 h. 9.00 - 13.00
Sala Videoconferenze

The focus of the course is on the design and analysis of algorithms for fundamental combinatorial optimization problems.
We start with a review of the most widely applied paradigms in practice:

 1) The efficient treatment of recursive problems via     divide and conquer methods and dynamic programming.

 2) Max flow / Min Cut and the use of transportation     networks for modelization in computer science.
When exact solutions are out of practical reach, a natural idea is to resort on controled approximations:

 3) Approximation algorithms: greedy technics;     linear programming and rounding methods.
While aiming at efficient algorithmic solutions, it is fundamental to realize that some problems are intrinsically more difficult than others, and cannot be solved by brute force:

 4) NP completeness and the limits of approximability. Finally we arrive to more advanced and recent methods:

 5) Parametric complexity and ways to understand the origin     of combinatorial explosion and deal with it.

 6) Primal/dual methods for approximation and the     competitivity analysis of online algorithms.



PhD Students/Alumni

Dip. Ingegneria dell'Informazione e Scienze Matematiche - Via Roma, 56 53100 SIENA - Italy