ORCO

Login

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

Last modified on September 19, 2022, at 06:51 PM