Volumes horaires
- CM 36.0
- Projet -
- TD -
- Stage -
- TP -
- DS -
Crédits ECTS
Crédits ECTS 6.0
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.
PrérequisBasic 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.