Combinatorial optimization and graph theory - WMM9CO02

Objectif(s)

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.

Responsable(s)

Zoltan SZIGETI

Contenu(s)

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.

Basic knowlegde of Graph Theory and Linear Programming

Contrôle des connaissances

Evaluation : 20% de Examen oral (exposé, soutenance, etc..) et 80% de Examen Ecrit (2h)

Rattrapage : 20% de Examen oral (exposé, soutenance, etc..) (note reportée) et 80% de Examen écrit + examen oral (3h)

L'examen existe uniquement en anglais

Calendrier

Le cours est programmé dans ces filières :

• Parcours de master - Master Informatique - Semestre 9 (ce cours est donné uniquement en anglais)
• Parcours de master - Master Math. et Applications - Semestre 9 (ce cours est donné uniquement en anglais)

Informations complémentaires

Code de l'enseignement : WMM9CO02
Langue(s) d'enseignement :

Vous pouvez retrouver ce cours dans la liste de tous les cours.