18.433 Combinatorial Optimization Schedule for Fall 2005

Date Topic Reading/Handouts PSets
Th Sept 8 Introduction matching example, spanning tree game PS1 out
Tu Sept 13 Bipartite matching (cardinality) lecture notes
Th Sept 15 Assignment problem lecture notes, section 4.4 in book PS1 due, solns
Tu Sept 20 Non-bipartite matching (cardinality) lecture notes, section 4.3 in book
Th Sept 22 Linear programming, systems of linear inequalities lecture notes, sections 0.1, 0.2 in book PS2 out
Tu Sept 27 LP duality, polyhedra (faces, dim, ...) lecture notes, sections 0.5 in book
Th Sept 29 Polyhedral Combinatorics, descriptions of polyhedra lecture notes PS2 due, solns
Tu Oct 4 Total Unimodularity section 3 of matching notes, section 0.8 of book PS3 out
Th Oct 6 Matroids sections 1.1, 1.4 of book
Tu Oct 11 Columbus Day
Th Oct 13 Matroids: Greedy algorithm, circuits, representation sections 1.2, 1.3, 1.4 of book PS3 due, solns
Tu Oct 18 Matroids: rank, matroid polytope sections 1.5, 1.7 of book PS4 out
Th Oct 20 Intersection of matroids: applications section 3.1 in book
Tu Oct 25 Minimum cost arborescences lecture notes
Th Oct 27 Intersection of matroids: cardinality algorithm section 3.2 in book PS4 due, solns
Tu Nov 1 Matroid union, packing bases notes
Th Nov 3 Review
Tu Nov 8 --
Th Nov 10 Quiz
Tu Nov 15 Maximum Flow problem Chapter 5
Th Nov 17 Minimum Cut Problem minimum cut notes PS5 out
Tu Nov 22 Ellipsoid algorithm for LP ellipsoid notes
Th Nov 24 Thanksgiving
Tu Nov 29 Ellipsoid algorithm in Comb Opt ellipsoid notes
Th Dec 1 Min T-odd cut, Matching Polytope PS5 due, PS5 solns, PS6 out
Tu Dec 6 Traveling Salesman Problem Chapter 7 in Cook et al.
Th Dec 8 Traveling Salesman Problem Chapter 7 in Cook et al. PS6 due
Tu Dec 13 Review