2015HS: 53085 Combinatorial Optimization, Graphs and Applications

With this course, the students will get familiar with the basic notions and fundamental problems in combinatorial optimization and graph theory. They will learn how to use these theoretical problems to model real world problems as well as how to solve them. Also, they will see different types of algorithms and learn how to prove the correctness of an algorithm. In this course, we introduce some basic concepts and problems in combinatorial optimization, most of them being related to graph theory. In a first part, we recall the most important notions in graph theory and in computational complexity. Various types of algorithms are introduced and illustrated via concrete examples (like for instance exact algorithms, greedy algorithms, approximation algorithms, dynamic programming). In a second part, we focus on some well known problems in combinatorial optimization (like for instance minimum spanning tree, shortest path, network flow, graph coloring). We introduce the corresponding theory, analyse the algorithms and present some applications of these problems. The students will also learn how to model real world problems using these graph theoretical problems.