Combinatorial Optimization - Teaching material - Ilan Newman


Office hours: Tue 10-11

Syllabus .

Books:

We will primarly use the 3 vols "Combinatorial Optimization" by Schrijver .

Exercises:

Updated ILP definition for EX1, and ex 1.7 :includes also EX6 .

My notes (in Hebrew) - will be updated as we proceed

  • Matching in bipartite and general graphs .
  • LP and polyhedral combinatorics .
  • Separation Oracle for the matching polytope

    Some pointers to Internet courses / links:

  • A course of Chandra Chekuri on the same topic. .
  • Material of Michel Goemans on Compbinatorial Optimization, see especially material linear porgramming and polyhedral combinatorics..
  • A course by Santosh Vempala. - All the material on combinatorial matching algorithm that was covered in lecture 1,2 is in here (lec. 123)
  • Matroid Intersection - the proof of Woodall
  • Applets demonstrating the Hungarian methods for bipartite matching and matching in general graphs
  • Goemans course: matching polytope.
  • Material of Michel Goemans on Matroids.
  • Material of Michel Goemans on Matroids Intersection.