- The Design of Approximation Algorithms by David P. Williamson,
David B. Shmoys (WS) (online copy)

- Approximation Algorithms by Vijay Vazirani (VV)
- Approximation Algorithms for NP-hard Problems by Dorit Hochbaum (DH)

Top

- Assignments: 20
- Seminar: 20
- Midsem: 20
- Endsem: 40

Any other form of copying implies a fail grade in the course. If you get stuck while solving the assignment, you are welcome to discuss with me.

Top

Assignment 1

Assignment 2

Assignment 3

Assignment 4

Top

Top

- 7 Aug: Introduction, vertex cover: greedy algorithm, 2-approximation algorithm. (Ref: VV, and this)
- 14 Aug: Set cover: greedy algorithm, 2-approximation for weighted vertex cover by layering technique (Ref: VV Chapter 2)
- 16 Aug: Steiner tree: Reduction to metric case, 2-approximation by MST (VV Chapter 3)
- 23 Aug: Traveling Salesman Problem: 2-approximation and 3/2-approximation (Christofide's algorithm) (VV Chapter 3)
- 28 Aug: Knapsack problem: Greedy algorithm for fractional knapsack, 2-approximation to 0/1 knapsack via modified greedy, PTAS (ref)
- 30 Aug: Knapsack problem: pseudopolynomial time algorithm using dynamic programming, FPTAS. Discussion: strong NP-hardness, existence of pseudopolynomial time algorithms and FPTAS. (VV Chapter 8)
- 11 Sep: Scheduling on identical parallel machines: greedy (2-approximation) LPT (4/3-approximation), PTAS (WS Chapter 2,3)
- 13 Sep: PTAS for scheduling on identical parallel machines continued, Introduction to LP, duality, Basic techniques illustrated through set cover: deterministic rounding (VV Chapter 12, WS Chater 1, WS Appendix A for a quick overview of LP)
- 13 Sep: Basic techniques: set cover by dual rounding, primal-dual method, randomized rounding (WS Chapter 1)
- 17 Sep: Randomized rounding for set cover continued, set cover by dual fitting (WS Chapter 1)
- 18 Sep: Bin packing: Greedy, inapproximility, APTAS (Section 3.3 of WS)
- 20 Sep: Local search: Max cut, introduction to submodular functions (Ref)
- 20 Sep: Local search: Submodular function maximization (Ref)
- 2 Oct: Midsem discussion, Clustering and location problems: 2-approximation for metric k-center (Section 2.2 of WS)
- 2 Oct: Inapproximability for metric k-center, introduction to uncapacitated facility location: 4-approximation by LP rounding (Section 4.5 of WS)
- 4 Oct: Uncapacitated Facility location continued: LP deterministic and randomized rounding (Sections 4.5,5.8 of WS)
- 4 Oct: Improved randomized rounding for uncapacitated facility location (Section 12.1 of WS)
- 18 Oct: Steiner forest problem: Primal-Dual algorithm (Section 7.4 of WS)
- 23 Oct: Steiner forest problem continued
- 24 Oct: Cuts and metrics: Multiway cut problem 2-approximation (Section 8.1 of WS)
- 25 Oct: Multiway cut: 3/2 approximation (Section 8.2 of WS)
- 25 Oct: Application of tree metrics: Buy-at-bulk network design (Section 8.6 of WS)
- 1 Nov: Approximate counting (Lecture by Partha, reference)
- 8 Nov: Solving linear programs by ellipsoid method (Lecture by Muthuvel, reference
- 15 Nov: Semidefinite programming: Application to MAX CUT (WS Chapter 6)
- 15 Nov: Embedding into l_1 and application to sparsest cut (WS Chapter 15)
- 20 Nov: Inapproximability (WS Chapter 16, ref)

Top