401-4904-00L Combinatorial Optimization
Semester | Spring Semester 2017 |
Lecturers | R. Zenklusen |
Periodicity | yearly recurring course |
Language of instruction | English |
Abstract | 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). |