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.