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 plan to talk more about matroids.
If there is time left, we will talk about submodular functions.
The project is here.
The exercise is here.
The notes of the first three lectures
are here. Thank so much
to Lionel Zoubritzky for taking the trouble.