Advanced Algorithms

I plan to cover some examples illustrating the advanced techniques in algorithm design, for example, uses of linear programs, randomization etc. The topics will be somewhat different from the 2019 version of the course.

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

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.
Problem set

Top

Lectures

    Module 1: Approximation Algorithms

  1. Aug 9: Introduction to approximation algorithms, optimization vs decision problems, vertex cover 2-approximation (Ref: Chapter 1 from [VV])
  2. Aug 16: Greedy algorithm for set cover (Ref: Section 2.1 of [VV])
  3. 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])
  4. 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])
  5. Aug 25: Job scheduling continued. PTAS by rounding and dynamic programming (Section 3.2 of [WS])
  6. Aug 30: Bin packing, 2-approximation by first fit, 3/2 inapproximability and APTAS (Section 3.3 of [WS])
  7. Sept 1: Introduction to LP, LP vs ILP optimum, integrality gap, LP rounding for weighted vertex cover (Ref)
  8. Sept 6: Uncapacitated facility location problem: 6-approximation, improvement to 4-approximation (Ref)
  9. 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])
  10. 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])
  11. 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])
  12. Sept 15: Primal-dual algorithm for 2-approximation of weighted vertex cover (Ref)
  13. Sept 20: Primal-dual algorithm for shortest path (Ref), Steiner tree, reduction of general case to metric case (Section 3.1 of [VV])
  14. 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])

    15. Module 2: Flows and Cuts


  15. 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)
  16. Oct 18: Max-flow min-cut theorem, Faster min-cut by Karger and Stein( Same ref as above)
  17. Oct 20: Edmonds-Karp algorithm for max-flows, generalizations, applications to edge-disjoint paths and bipartite matchings (Ref: CLRS book)
  18. 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)
  19. Oct 27: Multiway cut problem: 2-approximation by min weight isolating cuts, LP for multiway cut (Ref: Sections 8.1,8.2 of [WS])
  20. Oct 30: Randomized rounding for multiway cut: 3/2 approximation (Section 8.2 of [WS]
  21. Nov 1: Minimum k-cut: 2(1-1/k) approximation using Gomory-Hu trees (Ref)
  22. Nov 3: Existence of Gomory-Hu trees from submodularity of cuts (Ref)
  23. Nov 8: Network reliability: Unbiased estimator min-cut (this ref and this one)
  24. Nov 10: Network reliability continued. DNF counting (Ref as above)

    25. Module 3: Miscellaneous topics


  25. Nov 15: Lovász Local Lemma: Non-constructive version, application to k-SAT (Ref)
  26. Nov 17: Algorithmic Lovász Local Lemma (Ref)
  27. 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])
  28. Nov 22: Inapproximability of MAX-E3SAT from PCP theorem (Ref: Theorem 16.22 from [WS])

Relevant interesting papers