Linear Programming and Combinatorial Optimization, November 2022 - February 2023

by Uri Feige

Lecture notes and homework assignments appear below, and more will be added.
Students may look up the topics of the course in other sources, such as the book Understanding and Using Linear Programming, by Gartner and Matousek (Springer 2007).
The teaching assistant is Vadim Grinberg. vadim.grinberg@weizmann.ac.il. Please hand in homework assignments in English.

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

A short summary of the course

If you find errors in lecture notes or homework, please let me know.