18.997: Topics in Combinatorial Optimization, Spring 2004
The course homepage is now archived on OCW.
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.
Scribe Notes:
For scribes, here is the preamble.tex,
sample scribe
notes with a figure.
Label figures lecXX-name.eps.
- 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.