Instructor: Michel Goemans.

Tuesdays and Thursdays 1:00PM-2:30PM in 2-151. First meeting Feb 3rd, 2004.

In this course, we will be covering advanced topics in combinatorial optimization. The textbook is the 3-volume book by Lex Schrijver "Combinatorial Optimization: Polyhedra and Efficiency" (published by Springer-Verlag and available with a 10% discount from Quantum Books ), but we will be covering only some of the 83 chapters... This is a marvelous book with lots of results, references and concise proofs. I will assume familiarity with many basic results in combinatorial optimization.

Here is a preliminary (and partial) list of topics to be discussed:

- Ear decompositions.
- Nonbipartite matching.
- Gallai-Milgram and Bessy-Thomasse theorems on partitioning/covering graphs by directed paths/cycles.
- Minimization of submodular functions.
- Matroid intersection. Polymatroid intersection.
- Jump systems.
- Matroid union.
- Matroid matching, path matchings.
- Packing trees and arborescences.
- Packing directed cuts and the Lucchesi-Younger theorem.
- Submodular flows and the Edmonds-Giles theorem.
- Graph orientation.
- Connectivity tree and connectivity augmentation.
- Multicommodity flows.

- February 3rd, 2004. Lecture 1. Non-bipartite matching: Tutte-Berge formula, Gallai-Edmonds decomposition, blossoms.
- February 5th, 2004. Lecture 2. Non-bipartite matching: Edmonds' cardinality algorithm and proofs of Tutte-Berge formulas and Gallai-Edmonds decomposition.
- February 10th, 2004. Lecture 3. Cubic graphs and matchings, Factor-critical graphs, ear decompositions.
- February 12th, 2004. Lecture 4. Total dual integrality, Hilbert bases.
- February 17th, 2004. Monday schedule. No classes.
- February 19th, 2004. No classes.
- February 24th, 2004. Lecture 5. Total dual integrality, totally unimodularity. Matching polytope and the Cunningham-Marsh formula showing TDI.
- February 26th, 2004. Lecture 6. Posets and Dilworth theorem. Deduce Konig's theorem for bipartite matchings. Weighted posets and the chain and antichain polytopes.
- March 2nd, 2004. Lecture 7. Partitioning digraphs by paths and covering them by cycles. Gallai-Milgram and Bessy-Thomasse theorems. Cyclic orderings.
- March 4th, 2004. Lecture 8. Proof of the Bessy-Thomasse result. The cyclic stable set polytope.
- March 9th, 2004. Lecture 9. Matroids: defs, dual, minor, representability.
- March 11th, 2004. Lecture 10. Matroids: representability, greedy algorithm, matroid polytope.
- March 16th, 2004. Lecture 11. Matroid intersection.
- March 18th, 2004. Lecture 12. Matroid intersection, matroid union, Shannon switching game.
- March 23th, 2004. Spring break.
- March 25th, 2004. Spring break.
- March 30th, 2004. Lecture 13. Matroid intersection polytope, matroid union.
- April 1st, 2004. Lecture 14. Matroid union, packing and covering with spanning trees, strong basis exchange properties.
- April 6th, 2004. Lecture 15. Matroid matching: examples, complexity, Lovasz's minmax relation for linear matroids.
- April 8th, 2004. Lecture 16. Jump systems: definitions, examples, operations, optimization, and membership.
- April 13th, 2004. Lecture 17. Jump systems: membership (cont'd). No scribe notes yet.
- April 15, 2004. Lecture 18. Graph orientations, directed cuts (Lucchesi-Younger theorem), submodular flows.
- April 22nd, 2004. Lecture 19. Submodular flows: examples, Edmonds-Giles theorem, reduction to matroid intersection in special cases.
- April 27th, 2004. Lecture 20. Splitting off. $k$-connectivity orientations and augmentations.
- April 29th, 2004. Lecture 21. Proof of splitting-off. Submodular function minimization.
- May 11th, 2004. Lecture 22. Multiflow and disjoint path problems. Two-commodity flows.
- May 13th, 2004. Lecture 23. The Okamura-Seymour theorem and the Wagner-Weihe linear-time algorithm.