401-4904-00L  Combinatorial Optimization

SemesterSpring Semester 2017
LecturersR. Zenklusen
Periodicityyearly recurring course
Language of instructionEnglish


AbstractCombinatorial 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.
ObjectiveThe 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.
ContentKey topics include:
- Polyhedral descriptions;
- Combinatorial uncrossing;
- Ellipsoid method;
- Equivalence between separation and optimization;
- Design of efficient approximation algorithms for hard problems.
Lecture notesNot 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 / NoticeWe recommend that students interested in Combinatorial Optimization first attend the course "Mathematical Optimization" (401-3901-00L).