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:
• [VV] Approximation algorithms by Vijay Vazirani
• [WS] The design of approximation algorithms by Williamson, Shmoys
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.

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

### 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