Meeting times

Just a gentle reminder that we meet Mondays and Wednesdays from 2:30-4:00pm in Bell 242. In particular, we meet today (i.e. Aug 31). Also for student presentations, we will meet till 4:30pm.

Plan for the LP-half of the course

This plan is only tentative. I have about 7 weeks to finish the following points.

1. Brief introduction to approximation algorithms, motivate the use of linear programming: vertex-cover is the prototypical example. Then, a brief introduction to linear programming (LP). What it is. Known methods to solve it.
2. Structures of LP solutions, some geometric intuition. Basic feasible solutions (bfs, also called extreme point solutions) and intuition of the simplex method.
3. Farkas Lemma & LP Duality. Proof of strong duality. Complementary slackness. The primal-dual algorithm.
4. Integer linear programming (ILP) and its relationship to LP: total unimodularity, integrality gap and its relation to approximation algorithms. In terms of total unimodularity, talk about how some combinatorial optimization problems (weighted bipartite matching, max-flow & min-cut, shortest path, Hichcock problem) can be solved by solving LPs.
5. Ellipsoid method & separation oracles.
6. Rounding.
7. Randomized rounding.
8. Iterative rounding.
9. Primal-dual method.
10. Dual-fitting.