- [VV] Approximation algorithms by Vijay Vazirani
- [WS] The design of approximation algorithms by Williamson, Shmoys

Assignment 1 due on September 3.

Assignment 2 due on October 3.

Assignment 3 due on November 26

Top

- August 7: Introduction to approximation algorithms, 2-approximation for vertex cover, greedy algorithm for set cover [VV]
- August 9: Analysis of greedy set cover: O(log n) approximation, inapproximability of the traveling salesman problem [VV,WS]
- August 14: 2-approximation for metric TSP, 3/2-approximation by Christofide's algorithm (Technique: Use of two lower bounds)[VV]
- August 16: Local search: 2-approximation to List scheduling (minimum makespan), list scheduling using LPT rule: 4/3 approximation [WS]
- August 21: List scheduling by LPT rule continued, definition of PTAS, PTAS for list scheduling with constant number of machines[WS]
- August 23: PTAS for list scheduling by rounding[WS]
- August 28: Bin-packing: Hardness, inapproximability, first-fit algorithm and analysis, APTAS
- September 4: Introduction to LP, deterministic rounding for weighted vertex cover, introduction to duality
- September 6: Strong duality and complementary slackness condition (without proof), primal-dual algorithm for weighted vertex cover (Ref)
- September 11: Steiner tree 2-approximation, LP formulation for prize-collecting Steiner tree (Ref: [VV] for 2-approximation, [WS] for LP formulation)
- September 13: Prize-collecting Steiner tree: 3-approximation by deterministic rounding of LP (Ref: [WS])
- September 18: Prize-collecting Steiner tree continued: solving the LP by ellipsoid method, polynomial-time separation oracle for the prize-collecting Steiner tree LP (Ref: [WS])
- September 20: Steiner tree primal-dual algorithm (Ref: [WS])
- October 4: Introduction to randomized algorithms, randomized 2-approximation to weighted MAX-SAT, derandomization using conditional expectation (Ref: [WS])
- October 9: Improving the approximation for weighted MAX-SAT using biased coins, further improvement using randomized LP rounding ([WS])
- October 11: Improved approximation for prize-collecting Steiner tree using randomization [WS], Karger's min-cut algorithm (Ref)
- October 16: Faster min-cut algorithm by Karger and Stein (Ref as before, and this)
- October 18: Network reliability (Ref)
- October 23: Network reliability continued
- October 25: Enumerating small cuts: Coupon-collector paradigm, FPRAS for DNF counting (Ref)
- October 30: Polynomial identity testing and its application to bipartite matchings (Refand this) November 6: Problem Discussion: k-center 2-approximation, matchings in general graphs using PIT
- November 8: Isolation lemma, bipartite matchings in RNC
- November 13: Lovász Local Lemma: Non-constructive proof and application to k-CNF SAT (Ref)
- November 15: Algorithmic Lovász Local Lemma: randomized k-SAT (Ref: As above)
- November 20: Online bipartite matching (Original paper and this paper for the proof presented in class)
- November 22: Online bipartite matching continued