Combinatorial Optimization (2023)
General Information: the course will mostly
draw material from the following two books.
- Combinatorial Optimization, by Cook, Cunningham, Pulleyblank
and Schrijver.
- Network flows: theory, algorithms, and applications,
by Ahuja, Magnanti, and Orlin.
- September 28. We talked about the preflow-push algorithm and Edmonds-Karp
algorithm for maximum flow.
- October 5. We presented an algorithm for maximum density subgraph
problem. We then presented Berge's theorem, Konig's theorem and
Egervary's theorem.
The first homework exericse is here.
The solution is here.
- October 12. We talked about Karger's min-cut algorithm and Gomory-Hu trees.
- October 19. We presented Edmonds' blossom algorithm.
- October 25. It is about the matroids. The second homework exericse is here. The solution is here.
- November 9. We talk about multi-commodity flow and k-coverage problems.