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, Matej Stehlik, Myriamm Preissmann, Louis Esperet, Frédéric Maffray,

Last modified on April 22, 2016, at 08:44 AM