In this seminar we will discuss selected topics in discrete optimization. The main focus is on modern approaches to combinatorial optimization, including linear programming and polyhedral methods. Additional topics include approximation algorithms and online/streaming algorithms.
The goal of the seminar is twofold. On the one hand, the students will learn and practice presenting scientific papers to an audience. On the other hand, the students will be exposed to cutting-edge research in the field of combinatorial optimization. An active participation in the seminar should allow the student to later read and understand a paper in the topic of discrete optimization independently. Students intending to do a project in optimization are strongly encouraged to participate.
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.