- Assumed background
- References
- Evaluation
- Assignments
- Practice Problems
- Lectures
- Relevant interesting papers

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

Problem set

Top

- Aug 9: Introduction to approximation algorithms, optimization vs decision problems, vertex cover 2-approximation (Ref: Chapter 1 from [VV])
- Aug 16: Greedy algorithm for set cover (Ref: Section 2.1 of [VV])
- Aug 18: The traveling salesman problem (TSP), inapproximability, 2-approximation using MST lower bound, Christofide's algorithm for 3/2-approximation (Ref: Section 2.4 of [WS])
- Aug 23: Job scheduling on identical parallel machines: 2-approximation by greedy/local search, 4/3-approximation by longest job first (LPT) rule (Section 2.3 of [WS])
- Aug 25: Job scheduling continued. PTAS by rounding and dynamic programming (Section 3.2 of [WS])
- Aug 30: Bin packing, 2-approximation by first fit, 3/2 inapproximability and APTAS (Section 3.3 of [WS])
- Sept 1: Introduction to LP, LP vs ILP optimum, integrality gap, LP rounding for weighted vertex cover (Ref)
- Sept 6: Uncapacitated facility location problem: 6-approximation, improvement to 4-approximation (Ref)
- Sept 8: Introduction to randomization, 2-approximation to MAX-CUT and 8/7-approximation to MAX-3SAT, derandomization using conditional expectation (Ref: Sections 5.1,5.2 of [WS])
- Sept 11: (Extra class) Better approximations to MAX-SAT: 0.618 via biased coins, (1-1/e) via randomized rounding of LP solution (Sections 5.3,5.4 of [WS])
- Sept 13: Better of the two: 3/4 approximation for MAX-SAT (Section 5.5 of [WS]), Introduction to LP-duality, weak and strong duality, complementary slackness (Ref: Any book/notes on LP duality e.g. Appendix A of [WS])
- Sept 15: Primal-dual algorithm for 2-approximation of weighted vertex cover (Ref)
- Sept 20: Primal-dual algorithm for shortest path (Ref), Steiner tree, reduction of general case to metric case (Section 3.1 of [VV])
- Sept 22: 2-approximation to Steiner tree (Ref: Section 3.1 of [VV]) and primal-dual algorithm for generalized Steiner tree problem (Section 7.4 of [WS])
- Oct 11: Introduction to network flows: Ford-Fulkerson algorithm, Karger's algorithm for global min-cut (Ref: CLRS book for network flows, these notes for Karger's algorithm)
- Oct 18: Max-flow min-cut theorem, Faster min-cut by Karger and Stein( Same ref as above)
- Oct 20: Edmonds-Karp algorithm for max-flows, generalizations, applications to edge-disjoint paths and bipartite matchings (Ref: CLRS book)
- Oct 25: Dinic's algorithm for max-flow, minimum cost flows by choosing a minimum cost augmenting path, overview of the minimum mean-cycle cancelling algorithm (ref for Dinic's algorithm, ref for min-cost flows)
- Oct 27: Multiway cut problem: 2-approximation by min weight isolating cuts, LP for multiway cut (Ref: Sections 8.1,8.2 of [WS])
- Oct 30: Randomized rounding for multiway cut: 3/2 approximation (Section 8.2 of [WS]
- Nov 1: Minimum k-cut: 2(1-1/k) approximation using Gomory-Hu trees (Ref)
- Nov 3: Existence of Gomory-Hu trees from submodularity of cuts (Ref)
- Nov 8: Network reliability: Unbiased estimator min-cut (this ref and this one)
- Nov 10: Network reliability continued. DNF counting (Ref as above)
- Nov 15: Lovász Local Lemma: Non-constructive version, application to k-SAT (Ref)
- Nov 17: Algorithmic Lovász Local Lemma (Ref)
- Nov 20: Inapproximability of maximum independent set by reduction from MAX-E3SAT, statement of the PCP theorem (Ref: Theorems 16.8 and 16.12, Section 16.3 from [WS])
- Nov 22: Inapproximability of MAX-E3SAT from PCP theorem (Ref: Theorem 16.22 from [WS])