Research Institute for Discrete Mathematics
Lecture Course "Combinatorial Optimization"
Winter Term 2024/25
This is the introductory module in area C (Discrete Mathematics)
of the Master's Programme in Mathematics.
It is also an introductory module in the area "Algorithmics"
of the Master's Programme in Computer Science.
This course should be attended by
beginning master's students (unless they focus on other areas).
Basic knowledge in combinatorial algorithms,
in particular graphs, network flows, and linear programming, is required
(if you understand the contents of Sections 3.4, 7.1, 8.1, 8.2, 8.3, 9.1, 9.2, 9.4, 10.1, 11.1, and 15.3.
of the Korte–Vygen book cited below, you are ready to take this course).
This course covers the following topics:
connectivity in graphs, Gomory–Hu trees, nonbipartite matching,
Edmonds' weighted matching algorithm,
generalized matching problems, T-joins and T-cuts, submodular functions,
network design, traveling salesman problem, polyhedral combinatorics.
Some additional topics may be covered as well, including very recent results.
This course is in English. Most of it will be based on the following book:
- B. Korte, J. Vygen :
Combinatorial Optimization: Theory and Algorithms.
Springer,
Sixth edition 2018
(see here for more information)
Other recommendable books:
- A. Schrijver : Combinatorial Optimization: Polyhedra and Efficiency.
Springer 2003
- A. Frank: Connections in Combinatorial Optimization.
Oxford University Press, 2011
- W. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver: Combinatorial Optimization.
John Wiley & Sons, 1996
These books (and many others) are available in our library.
| First class: | Tuesday, October 8. Attend to take part in the assignment to exercise groups!
|
| Class Hours: | Tuesdays and Thursdays 2–4 pm (14:15–15:45)
|
| Exercise Classes: | two hours per week, t.b.a.
|
| Room: | Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)
|
| Exams: | t.b.a.
|
Prof. Dr. J. Vygen