This information is indicative and can be subject to change.
Combinatorial optimization
Teacher: Alexandre Skoda
E-mail: askoda@univ-paris1.fr
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:
• Maximum flow, minimum cut, Ford-Fulkerson algorithm.
• Matchings in bipartite graphs, hungarian method.
• General matchings, Edmonds algorithm.
References:
Combinatorial optimization
Teacher: Alexandre Skoda
E-mail: askoda@univ-paris1.fr
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:
- Introduction to graph theory
- Introduction to linear programs
- Graph Theory and algorithmic applications:
• 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.
