401-4904-00L  Combinatorial Optimization

SemesterFrühjahrssemester 2019
DozierendeR. Zenklusen
Periodizitäteinmalige Veranstaltung

KurzbeschreibungCombinatorial 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.
LernzielThe 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.
InhaltKey topics include:
- Polyhedral descriptions;
- Combinatorial uncrossing;
- Ellipsoid method;
- Equivalence between separation and optimization;
- Design of efficient approximation algorithms for hard problems.
SkriptLecture notes will be available online.
Literatur- Bernhard Korte, Jens Vygen: Combinatorial Optimization. 5th edition, Springer, 2012.
- Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003. This work has 3 volumes.
Voraussetzungen / BesonderesPrior exposure to Linear Programming can greatly help the understanding of the material. We therefore recommend that students interested in Combinatorial Optimization get familiarized with Linear Programming before taking this lecture.