Convex and Combinatorial Optimization (second part)
- Nov 9: we presented Hopcroft-Karp algorithm for bipartite matching.
König's theorem, Egerváry's theorem were proved.
Finally the Kuhn's Hungarian algorithm was shown.
- Nov 17: Simplex method and linear programming duality
- Nov 23: Edmonds' blossom algorithm along with three different
proofs were presented. Tutte-Berge mini-max formula was also proved.
- Nov 30: we presented an algebraic algorithm based on Tutte's
matrix to compute the cardinality of a maximum matching.
Gomory-Hu trees were presented as well.
- Dec 7: we gave an introduction on matroids:
various characterizations of matroids; greedy algorithm;
Edmonds' description of independent sets by linear constraints;
mini-max theorem of matroid intersection; a polynomial
time algorithm for finding the maximum cardinality common
- Dec 14: we finished the discussion on
matroids. We gave two greedy algorithms for maximising
a monotone submodular function under constraints.
The project is here.
The exercise is here.
The solution of the exercise is here.
The notes of the first three lectures
are here. Thank
Lionel Zoubritzky so much for taking the trouble.