Combinatorial Optimization (2024)
General Information: the course will mostly
draw material from the following two books.
- 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).
The first homework is here. And the second homework is here.
The hints for the first homework is here, and those for the second is here.