Combinatorial Optimization (2024)
General Information: the course will mostly
draw material from the following book:
- Combinatorial Optimization, by Cook, Cunningham, Pulleyblank
and Schrijver.
Notice that this year the classroom is Salle W and the starting
time is 15:30, instead of the usual 14:30.
- September 26. We talked about Goldberg's preflow-push algorithm
and Edmonds-Karp algorithm. (For referene, you can read Chapters 3.2 and
3.4 of the book by Cook et al.)
- October 3. We talked about Konig's theorem, Egervary's theorem, and
Kuhn's Hungarian method. (A very good reference for all these
is a paper
by Andras Frank.)
- October 10. We presented Edmonds' blossom algorithm.
(One can find the reference easily anywhere).
- October 17. We presented Hao-Orlin algorithm for s-cut
and Karger's global min-cut algorithm. (For reference,
you can check the book of David Willaimson "Network Flow
Algorithms", Chapter 3).
- October 24. We talked about matroids and matroid intersection.
(For referene, you can read Chapters 8.1-8.3 of
the book by Cook et al.)
- November 14. We discussed Gomory-Hu trees and also k-coverage problem.
(For the former, you can read Chapter 3.4 of David Willamson's book).