Course on Linear Programming and Combinatorial Optimization, March 2015 - June 2015

by Uriel Feige

Lecture notes:

Lecture 1,2 (15,22 March): The linear algebra of linear programs
Lecture 3 (29 March): The geometry of linear programs
Lectures 3-5 (29 March, 12 and 19 April): The Simplex algorithm
Lectures 6-8 (26 April, 3 and 10 May): Duality, total unimodularity
Lectures 8-10 (10, 17 and 31 May): The ellipsoid algorithm, embeddings into Euclidean space
Lectures 10-11 (31 May, 7 June): Perfect graphs and the theta function of Lovasz
Lectures 12 (21 June): Approximate coloring of 3-colorable graphs

Handouts (homework) for course.

Handout 1 (22 March): Basic feasible solutions
Handout 2 (19 April): Simplex algorithm. Klee-Minty Cube.
Handout 3 (3 May): LP duality. Helly's theorem. Total unimodularity.
Handout 4 (31 May): Ellipsoid algorithm, the Lovasz Theta function.
Handout 5 (21 June): Coloring 4-colorable graphs.
Handout 6 (28 June): The handout contains no homework, but rather a reminder of concepts and topics covered in the course, as well as some topics not covered and some open questions. In class we discussed two algorithms of Goemans and Williamson. One gives a 3/4 approximation for max sat using an LP relaxation [SIDMA 1994]. The other gives an 0.87856... approximation for max cut using an SDP relaxation [JACM 1995].

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