Fall'23: Linear Programming and its Application to Approximation Algorithms (CS 521)

Monday: 17:40-20:40
Fiber Optic Materials Research Building - Room EHA

This is a graduate course on linear programming. In the second half of the course we will focus on the application of linear programming to approximation algorithms.

Prerequisites: It will be helpful to have some background in algorithms/discrete math, but no formal prerequisite will be enforced. If you do not satisfy the official prerequisites but are still interested in registering for the course, and you are concerned if you will be sufficiently prepared for the course, please send me an email.
The only real prerequisite is mathematical maturity.


Please use this latex template for the scribes. All questions about the scribing must be directed to Lucy Martinez.

You may scribe in groups of size 1, 2, 3, or 4. At most two groups can scribe each of the lectures.

The scribes of the Monday lecture are due by Friday night of the same week. Please email your scribes to Lucy Martinez.

You will receive feedback on your scribes typically by the Sunday night of that week and you have 48 hours to submit your revised scribe which will then be evaluated.

A perfect scribing of the lecture with every missing detail from the lecture filled in will be given 300 points. A scribe which merely copies what is written on the board and does not add any additional context or details will be given at most 50 points.


Your grade is computed out of 1000 points (you may accumulate at most 1000 points; if you obtain more than 1000 points then it will be capped to exactly 1000 points).

You can accumulate at most 300 points from scribing lecture notes. The two midterms are assigned 300 points each and the final exam is assigned 300 points.

Your grade will be computed solely based on the sum of all the points acquired through scribing, midterms, and final exam. There are no other extra credits activities for the course. No exceptions.

Topics and schedule

Lecture # When Topic
Lecture 1 09/11 Fundamentals of Linear Programming
Lecture 2 09/18 Geometry of Linear Programs
Lecture 3 09/25 The Simplex Algorithm
Lecture 4 10/02 LP Duality
10/09 Midterm I
Lecture 5 10/16 Ellipsoid Algorithm
Lecture 6 10/23 Lower Bounds for the Extension Complexity of Polytopes
Lecture 7 10/30 Lower Bound for the Extension Complexity of TSP Polytope
Lecture 8 11/06 Linear Programs for Approximating TSP
Lecture 9 11/13 Approximating Covering Problems via LP Rounding
11/20 Midterm II
Lecture 10 11/27 Approximating Facility Location via LP Rounding
Lecture 11 12/04 Approximating Sparsest Cut via LP Rounding
Lecture 12 12/11 Semi Definite Programming: Approximating Max Cut
Final Exam