Approximation Algorithms

Summary: In this course we will cover advanced techniques of algorithm design. In particular, we will see techniques for designing approximation algorithms for NP-hard optimization problems.

Prerequisite: CS301 (Design and Analysis of Algorithms)

Grading: End-sem (45%), Min-sem (25%), assignments + presentation (30%)

References: Algorithm Design by Kleinberg-Tardos (KT), The Design of Approximation Algorithms by David P. Williamson and David Shmoys (WS) (pdf), Approximation Algorithms (V) by Vijay Vazirani, Iterative Methods in Combinatorial Optimization (LRS) (pdf).

Please find the seminar topics for students here.

Announcements:

• We first meet on April 6 at 11:30 AM at M3. See you there.

• 19/04/2021: The first assignment has been posted on the Google classroom.

Lectures:

• Lecture 1: Introduction, Max-flow setup, Ford-Fulkerson algorithm (KT: Chapter 7, Section 7.1)

• Lecture 2: Correctness of Ford-Fulkerson algorithm, Max-flow min-cut theorem (KT Chapter 7, Section7.2)

• Lecture 3: Proof of Max-flow min-cut theorem, Edmonds-Karp algorithm for max-flow (Section 3 of Notes of Roughgarden)

• Tutorial: Variants of max-flow, bipartite matching (KT Chapter 7, Section 7.5)

• Lecture 4: Introduction to Approximation algorithms, Set cover (WS: Section 1.1, Section 1.6)

• Lecture 5: Analysis of Set cover (WS: Section 1.6)

• Lecture 6: 2-approx for k-Center (WS: Section 2.2)

• Lecture 7: Finish k-center, 3/2-approx for Metric TSP (WS: Section 2.4)

• Lecture 8: Finish analysis of metric TSP (WS: Section 2.4)

• Lecture 9: Local search for max-cut

• Lecture 10: Finish local search for max-cut in unweighted and weighted graphs. Start local search for k-median. (Onenote notes)

• Lecture 11: Analysis of local search for k-median (WS: Section 9.2, Onenote notes)

• Lecture 12: Finish analysis of local search for k-median (WS: Section 9.2, Onenote notes)

• Lecture 13: Approximation algorithm for Knapsack (WS: Section 3.1, Onenote notes)

• Lecture 14: Finish analysis of knapsack, start machine scheduling (WS: Section 3.1, 3.2, Onenote notes)

• Lecture 15: Scheduling on identical machines (WS: Section 3.2, Onenote notes)

• Lecture 16: Finish scheduling, start LP (Onenotes notes)

• Lecture 17: 2-approx for vertex cover, LP for min-cost perfect matching in bipartite graphs (Onenote notes)

• Lecture 18: Finish LP for min-cost perfect matching in bipartite graphs (Onenote notes)

• Lecture 19: LP for UFL (Onenote notes)

• Lecture 20: Finish LP for UFL (Section 3 of this note from another course, Onenote notes)

• Lecture 21: General forms of LP (Lecture 1 from this course, Onenote notes)

• Lecture 22: Extreme point characterization of LP (Lecture 2 of this course, Notes)

• Lecture 23: LP Duality (Lecture 5 of this course, Notes)

• Lecture 24: Extreme point solutions for bipartite matching, Generalized assignment problem (Notes)

• Lecture 25: Finish Generalized assignment problem (WS Section 11.1, Notes)

• Lecture 26: Scheduling on unrelated parallel machines (Vazirani Chapter 17, Notes)

• Lecture 27: Iteratively rounding max-weight bipartite matching (Section 3.1 of LRS, Notes)

• Lecture 28: Randomized algorithms for 3-SAT, Randomized rounding of set cover (Section 5.1 and 1.5 of WS, Notes)

• Lecture 29: Primal-dual algorithm for set cover (Section 7.1 of WS, Notes)

• Lecture 30: Primal-dual algorithm for UFL (Chapter 24 of Vazirani, Notes)

• Lecture 31: Finish primal-dual analysis of UFL ((Chapter 24 of Vazirani, Notes)

• Lecture 32: SDP formulation for max-cut (Sections 6.1, 6.2 of WS, Notes)

• Lecture 33: SDP for max-cut, discussion on Ellipsoid method (Section 6.1,6.2 of WS, Notes)

• Lecture 34: Hyperplane rounding for max-cut (Section 6.1,6.2 of WS, Notes)

• Lecture 35: SDP of Coloring (Section 6.5 of WS, Notes)

• Lecture 36: Hardness of Approximation I: Gap-introducing reductions (Section 16.1 of WS, Notes)

• Lecture 37: Hardness of Approximation II: Gap-preserving reductions, PCP (Section 16.1, 16.2 of WS, Notes)

• Lecture 38: Hardness of Approximation III: Using PCP theorem (Sections 16.3 of WS, Notes)

• Presentations by Tanmay Panigrahi and Ajay Saipriya Sahoo, Shashank Shekhar and M Raj Abhishek, K Prahlad Narasimhan

• Presentations by Konthalapalli Hradini and Karan, Aditya Petety and Akshat Agrawal, and Dinesh Beniwal and Gautameshwar S

• Presentations by Aman Upadhyay and Adittya Pal, Deepak Kumar and Nalin Kumar, Saswat Kumar Pati and Shashank Saumya

• Presentations by Vaishali Agarwal, Patil Prathmesh Vinod, Diprupa Saha and E.A.Sreeram