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
Rooms in 25-26
- 25/09 H112
- 02/10 C101
- 09/10 H114
- 16/10 C101
- 23/10 C101
- 06/11 H208
- 13/11 C101
- 20/11 C101
- 27/11 H114
- 04/12 Amphi C
- 11/12 H208
- 18/12 H202
- 08/01 C101
- 15/01 C101
