Combinatorial Optimization

This course helps students to familiarize with mathematical modeling of combinatorial problems and offers them theoretical and practical skills so that they are able to choose the appropriate algorithmic technique for solving such problems. In particular, the course deepens the general algorithmic techniques such as branch and bound, dynamic programming, local search methods and metaheuristics. It Shows the limits of those classical techniques and focuses on recent research developments on the approximation algorithms (PTAS, FPTAS), the theory of local search, PLS-completeness, neighborhoods structure, exponential neighborhoods searchable in polynomial time and it establishes the connection between local search methods, game theory and the theory of landscapes.