##
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.