• Home
  • Courses
  • Timetable
  • Opportunities
  • Applying
  • Contact
  • Internship
  • Optimal transport
  • Algorithmic game theory
  • Neural network
This information is indicative and can be subject to change. 

Combinatorial optimization
​

Teacher:  Alexandre Skoda

E-mail:  [email protected]
ECTS: 2.5
Evaluation:   written exam
Previsional Place and time:  9 sessions (2h per session)

Prerequisites: basic concepts in Graph theory (Path, trees, greedy algorithm), and in Linear programming (simplex method).
Aim of the course: This course introduces classical methods and algorithms widely used in the analysis of networks and in optimization problems.
 Syllabus: 
  1. Introduction to graph theory
  2. Introduction to linear programs
  3. Graph Theory and algorithmic applications:
• Shortest path problem.
• Maximum flow, minimum cut, Ford-Fulkerson algorithm.
• Matchings in bipartite graphs, hungarian method.
• General matchings, Edmonds algorithm.
 
References:
  •  V. Chvatal, Linear Programming, Freeman, 1983.
  • M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979.
  •  A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
Powered by Create your own unique website with customizable templates.
  • Home
  • Courses
  • Timetable
  • Opportunities
  • Applying
  • Contact
  • Internship
  • Optimal transport
  • Algorithmic game theory
  • Neural network