Advanced Algorithms

I plan to cover some advanced techniques in algorithm design, for example, use of linear programs, randomization etc.



Assumed background

Students taking this course should have done one course on programming, and one on design and analysis of algorithms. I also expect familiarity with basic concepts in probability. Top

References

There is no single textbook for the course. We will initially cover material from the following books: I will post other references as and when I cover topics outside these books. Top

Evaluation

There will be two quizzes, a mid-semester exam, and an end-semester exam. Top

Practice Problems

Assignments

You are not supposed to discuss the assignments with anyone or refer to any source on the internet. Students found copying assignments from each other will get a fail grade. If you are stuck while solving the assignment, you are welcome to discuss with me. I will be glad to give hints so that you can proceed. Assignments submitted after the due date will not be accepted.

Assignment 1 due on September 3.
Assignment 2 due on October 3.
Assignment 3 due on November 26
Top

Lectures

    Module 1: Approximation Algorithms

  1. August 7: Introduction to approximation algorithms, 2-approximation for vertex cover, greedy algorithm for set cover [VV]
  2. August 9: Analysis of greedy set cover: O(log n) approximation, inapproximability of the traveling salesman problem [VV,WS]
  3. August 14: 2-approximation for metric TSP, 3/2-approximation by Christofide's algorithm (Technique: Use of two lower bounds)[VV]
  4. August 16: Local search: 2-approximation to List scheduling (minimum makespan), list scheduling using LPT rule: 4/3 approximation [WS]
  5. August 21: List scheduling by LPT rule continued, definition of PTAS, PTAS for list scheduling with constant number of machines[WS]
  6. August 23: PTAS for list scheduling by rounding[WS]
  7. August 28: Bin-packing: Hardness, inapproximability, first-fit algorithm and analysis, APTAS
  8. September 4: Introduction to LP, deterministic rounding for weighted vertex cover, introduction to duality
  9. September 6: Strong duality and complementary slackness condition (without proof), primal-dual algorithm for weighted vertex cover (Ref)
  10. September 11: Steiner tree 2-approximation, LP formulation for prize-collecting Steiner tree (Ref: [VV] for 2-approximation, [WS] for LP formulation)
  11. September 13: Prize-collecting Steiner tree: 3-approximation by deterministic rounding of LP (Ref: [WS])
  12. 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])
  13. September 20: Steiner tree primal-dual algorithm (Ref: [WS])
  14. Module 2: Randomized Algorithms

  15. October 4: Introduction to randomized algorithms, randomized 2-approximation to weighted MAX-SAT, derandomization using conditional expectation (Ref: [WS])
  16. October 9: Improving the approximation for weighted MAX-SAT using biased coins, further improvement using randomized LP rounding ([WS])
  17. October 11: Improved approximation for prize-collecting Steiner tree using randomization [WS], Karger's min-cut algorithm (Ref)
  18. October 16: Faster min-cut algorithm by Karger and Stein (Ref as before, and this)
  19. October 18: Network reliability (Ref)
  20. October 23: Network reliability continued
  21. October 25: Enumerating small cuts: Coupon-collector paradigm, FPRAS for DNF counting (Ref)
  22. October 30: Polynomial identity testing and its application to bipartite matchings (Refand this)
  23. November 6: Problem Discussion: k-center 2-approximation, matchings in general graphs using PIT
  24. November 8: Isolation lemma, bipartite matchings in RNC
  25. November 13: Lovász Local Lemma: Non-constructive proof and application to k-CNF SAT (Ref)
  26. November 15: Algorithmic Lovász Local Lemma: randomized k-SAT (Ref: As above)
  27. November 20: Online bipartite matching (Original paper and this paper for the proof presented in class)
  28. November 22: Online bipartite matching continued