Approximation Algorithms



Assumed background

Students taking this course should have done one course on programming, and one on design and analysis of algorithms. Top

References

The course is based on the following books:
  1. The Design of Approximation Algorithms by David P. Williamson, David B. Shmoys (WS) (online copy)
  2. Approximation Algorithms by Vijay Vazirani (VV)
  3. Approximation Algorithms for NP-hard Problems by Dorit Hochbaum (DH)

Top


Evaluation

There will be four assignments, midsem, endsem, and seminar. The weightage is as follows:
  1. Assignments: 20
  2. Seminar: 20
  3. Midsem: 20
  4. Endsem: 40
Top

Copying policy

While solving the assignments (and class tests and exams too!), you are not supposed to discuss with anyone (neither in your class nor anyone else). If at all you discuss an assignment problem with someone, name of that person should be mentioned while writing the solution of that particular problem. If you look up the solution on the Internet, the link to the solution should also be mentioned while writing it.

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

Assignments

Note: Please read the Copying policy before you start solving the assignment. The solutions/hints will be posted on the deadline. Hence no late submissions are allowed.

Assignment 1
Assignment 2
Assignment 3
Assignment 4

Top

Marks



Top

Lectures

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

Top