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.
This is an advanced optimization course that builds upon "Mathematical Optimization" (401-3901-00L), which is a prerequisite for taking this lecture.
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.
The core topics of this lecture include:
- Polyhedral descriptions of combinatorial problems
- Combinatorial uncrossing
- Ellipsoid Method
- Equivalence between separation and optimization
- Design of efficient approximation algorithms for hard problems (if time permits)
- Bernhard Korte, Jens Vygen: Combinatorial Optimization. 5th edition, Springer, 2012.
- Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003. This work has 3 volumes.
The final exam is oral. Furthermore, there is an optional midterm exam that may improve the final grade.