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

Info

Structure




The Design And Analysis Of Algorithms For Combinatorial Optimization Problems

 

Prof.
Course Type
Group 2
Calendar
June 5-9 2017
Room
Program
Abstract:

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.





 

Courses

PhD Students/Alumni


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