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.

Diary of our class.

Nov 18: we talked about the preflow-push algorithm and also Berge's theorem on matching.

Nov 25: we talked about Konig's theorem, Egrevary's theorem and Hungarian method of Kuhn. We also explained how the linear programming duality comes into the picture.

Dec 2: we talked about the weighted-branching algorithm, Edmond's packing theorems of r-arboresences. We also talked about how to do the maximum weight matching in the streaming setting.

Dec 9: we talked about Edmonds' blossom algorithm. A variety of proofs were presented.

Dec 16: we talked about matroids and the intersection algorithm of Edmonds, along with a mini-max theorem of his.

Jan 6: we talked about Nagamochi-Ibaraki algorithm and Karger's contraction algorithm for computing global min-cut. An introduction to submodular functions was also given.

The first homework is here. The second homework is here. The solution to the first homework is here. The solution to the second homework is here.