November 9. The Linear Algebra of Linear Programs
Lecture
Homework
November 30. The Geometry of Linear Programs
Lecture
November 30 onwards. The Simplex Algorithm
Lecture
Homework
December 21 onwards. Linear Programming Duality
Lecture
Homework
January 4 onwards. The Ellipsoid Algorithm
Lecture
Homework
On January 25 there is no class. Use your free time to get at least a high level understanding of interior point methods, as these methods have both good theoretical guarantees and practical performance. Many overviews are available, including lecture by Christopher Musco, and Section 7.2 in the book of Gartner and Matousek. You are not required to read these (or other) overviews in full, but do read enough so as to get the general picture, and to at least know what the concepts of log barrier, analytic center and central path mean in the context of interior point methods.
January 18 onwards. Perfect graphs and the Lovasz theta function.
Lecture
Homework
February 8. Coloring 3-colorable graphs.
Lecture
Homework