Convex and Combinatorial Optimization (second part)
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.
- Oct 25 : we presented the generic pre-flow push algorithm
and the implementation based on highest-distance label.
- Nov 8 : we presented a max-flow algorithm
based on multiplicative weights update method.
Berge's theorem, Konig's theorem and Egavary's theorem are also discussed.
- Nov 15 : we present the Hungarian method
and an introduction to linear programming duality.
Two algorithms for min-cost flow (based on eliminating
negative cycle and on successive shortest path computations)
are discussed.
- Nov 22 : von Neumann's minimax theorem and
Edmonds' blossom algorithm are presented.
- Nov 29 : introduction of matroids.
Minimax theorem of matroid intersection and
Edmonds' algorithm for finding max-cardinality independent
set are presented.
- Dec 5 : introduction of submodular functions.
A greedy algorithm for submodular function maximisation
with cardinality constraint is presented.
The base exchange theorem and greedy
algorithm for matroid constraint are also discussed.
The exercise is here. Please hand in
your solution before the last class.
The solution is here.