ECTS : 5
Description du contenu de l'enseignement :
Volume horaire :
CM : 18h
TD : 18h
TP : 3h
This course studies solving optimisation problems using combinatorial methods. We will roughly follow the online textbook of Alexander Schrijver entitled “A course in Combinatorial Optimisation”. We start the course with the introduction of polyhedra and polytopes, Farkas’ Lemma and LP duality. Next we will study matching algorithms in bipartite graphs, general graphs as well as discuss weighted matchings and the matching polytope. Following this we will study aspects of Mengers’ theorem and its relation to flows. Next we will study algorithmic complexity, focusing mostly on the notion of NP-completeness and proving NP-completeness results. Finally, we will look at colorings, independent sets, posets and their role in optimisation problems. Time permitting, we will move into integer programming and totally unimodular matrices.
Compétence à acquérir :
Theoretical foundation of Linear Programming, Algorithmic Techniques, Applications
Bibliographie, lectures recommandées :
Reference text: Alexander Schrijver, “A course in Combinatorial Optimisation” available at https://homepages.cwi.nl/~lex/files/dict.pdf