Fall'23: Linear Programming and its Application to Approximation Algorithms (CS 521)
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.
Scribing
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.
Grading
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 |