Combinatorial Optimization and Graph Theory

The aim of this course is to provide a broad knowledge of fundamental problems in Combinatorial Optimization to show their algorithmic solutions and to derive min-max results on them. In order to achieve this goal a new object called a polyhedron is introduced. This polyhedral approach helps to shed new light on some classic results of Combinatorial Optimization.

Syllabus: Study of polyhedra associated to problems of Combinatorial Optimization ; Theory of blocking polyhedra ; Connectivity: shortest paths, spanning trees and spanning arborescences of minimum weight ; Flows: Edmonds-Karp Algorithm, Goldberg-Tarjan Algorithm, minimum cost flows ; Matchings: Hungarian method, Edmonds' Algorithm, Chinese postman problem; Matroids: greedy algorithm, intersection of two matroids ; Graph coloring ; Applications coming from various areas of Operations Research.

Coordinator: Zoltán Szigeti (zoltan.szigeti@grenoble-inp.fr)

Lecturers: Zoltán Szigeti, Moritz Muhlenthaler

Room :

29/09 C101
06/10 C319
13/10 C101
20/10 pas cours
27/10 C319
10/11 C101
17/11 C319
24/11 C319
01/12 C319
08/12 C319
15/12 C319
05/01 pas cours
12/01 C319
19/01 C319