Combinatorial Optimization deals with efficiently finding a provably strong solution among a finite set of options. This course discusses key combinatorial structures and techniques to design efficient algorithms for combinatorial optimization problems. We put a strong emphasis on polyhedral methods, which proved to be a powerful and unifying tool throughout combinatorial optimization.
Objective
The goal of this lecture is to get a thorough understanding of various modern combinatorial optimization techniques with an emphasis on polyhedral approaches. Students will learn a general toolbox to tackle a wide range of combinatorial optimization problems.
Content
Key topics include: - Polyhedral descriptions; - Combinatorial uncrossing; - Ellipsoid method; - Equivalence between separation and optimization; - Design of efficient approximation algorithms for hard problems.
Lecture notes
Not available.
Literature
- Bernhard Korte, Jens Vygen: Combinatorial Optimization. 5th edition, Springer, 2012. - Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003. This work has 3 volumes.
Prerequisites / Notice
We recommend that students interested in Combinatorial Optimization first attend the course "Mathematical Optimization" (401-3901-00L).
Performance assessment
Performance assessment information (valid until the course unit is held again)