Approximation Algorithms

Syllabus and References: We will primarily follow the textbook of Williamson and Shmoys. Recommended textbooks for the course include:
- The Design of Approximation Algorithms by David Williamson and David Shmoys, Cambridge University Press, 2011. http://www.designofapproxalgs.com/
- Approximation Algorithms by Vijay Vazirani, Springer-Verlag, 2004. https://www.ics.uci.edu/~vazirani/book.pdf
- Chandra Chekuri's Lectures. https://courses.engr.illinois.edu/cs583/fa2021/

Announcements

Lecture 01 (Jan 27, 2022): Introduction to approximation algorithms; greedy algorithms for unweighted set cover and max coverage problems; deterministic LP rounding for weighted set cover.
- Slides
- Video

Lecture 02 (Jan 28, 2022): Dual of an LP, weak duality theorem, strong duality theorem, f-approximation to weighted set cover by rounding a dual solution, complementary slackness, f-approximation to weighted set cover by the primal dual method
- Slides
- Video
- References: Sections 1.4 & 1.5 from Williamson & Shmoys (WS)
- Reading exercise: Section 1.6 in WS -- upto and including the proof of Theorem 1.11

Lecture 03 (Feb 03, 2022): Dual fitting & randomized rounding for weighted set cover
- Slides
- Video
- References: Sections 1.6 & 1.7 from Williamson & Shmoys (WS)

Lecture 04 (Feb 04, 2022): Greedy algorithms for k-Center problem and metric TSP; Christofides-Serdyukov algorithm for metric TSP
- Slides
- Video
- References: Sections 2.4 & 2.2 from Williamson & Shmoys (WS)
- Reading exercise: Inapproximability of general TSP -- Page 43 of [WS]

Lecture 05 (Feb 10, 2022): Minimum degree spanning tree algorithm; local search techniques
- Slides
- Video
- References: Sections 2.6 & 2.7 from Williamson & Shmoys (WS)

Lecture 06 (Feb 11, 2022): Edge coloring; greedy + local search
- Slides
- Video
- References: Sections 2.6 & 2.7 from Williamson & Shmoys (WS)

Lecture 07 (Feb 17, 2022): Dynamic Programming for Bin Packing
- Slides
- Video
- References: Section 3.1 from Williamson & Shmoys (WS)
- Reading Exercise: Section 3.10

Lecture 08 (Feb 18, 2022): Deterministic rounding of the LP solutions and Uncapacitated Facility Location Problem
- Slides
- Video
- References: Section 4.5 from Williamson & Shmoys (WS)
- Reading Exercise: Section 4.3

Lecture 09 (Feb 24, 2022): Bin packing approximation via deterministic LP rounding.
- Slides
- Video
- References: Section 4.6 from Williamson & Shmoys (WS)

Lecture 10 (Feb 25, 2022): Randomized Rounding schemes
- Slides
- Video
- References: Chapter 5 from Williamson & Shmoys (WS)

Lecture 11 (Mar 03, 2022): Semindefinite Programming and Shannon zero-error capacity
- Guest Lecturer: Prof. KV Subrahmanyam
- Slides
- Video
- References: Lovasz's book on Semidefinite Programming Semindefinite programming and combinatorial optimization.

Lecture 12 (Mar 04, 2022): Randomized Rounding and 3-approximation algorithm for Uncapacitated Facility Location
- Slides
- Video
- References: Section 5.8 and 5.11 from Williamson & Shmoys (WS)

Lecture 13 (Mar 10, 2022): Semindefinite Programming for Max-Cut
- Guest Lecturer: Prof. KV Subrahmanyam
- Slides
- Video
- References: Lovasz's book on Semidefinite Programming Semindefinite programming and combinatorial optimization.

Lecture 14 (Mar 11, 2022): Introduction to Hardness of Approximation and Unique Games Conjecture
- Slides
- Video
- References: Section 16.5 from Williamson & Shmoys (WS)

Lecture 15 (Mar 24, 2022): Primal Dual Technique
- Slides
- Video
- References: Chapter 7 from Williamson & Shmoys (WS)

Lecture 16 (Mar 31, 2022): Primal Dual algorithm for Uncapacitated Facility Location
- Slides
- Video
- References: Chapter 7 from Williamson & Shmoys (WS)

Lecture 17 (Apr 01, 2022): Cuts and Metrics 1: Multiway Cut
- Slides
- Video
- References: Chapter 8 from Williamson & Shmoys (WS) and Chapter 19 from Vazirani

Lecture 18 (Apr 07, 2022): Semindefinite Programming 3
- Guest Lecturer: Prof. KV Subrahmanyam
- Slides
- Video
- References: Lovasz's book on Semidefinite Programming Semindefinite programming and combinatorial optimization.

Lecture 19 (Apr 08, 2022): Cuts and Metrics 2: Multiway Cut continued
- Slides
- Video
- References: Chapter 8 from Williamson & Shmoys (WS) and Chapter 19 from Vazirani

Lecture 20 (Apr 21, 2022): Cuts and Metrics 3: Multicut
- Slides
- Video
- References: Chapter 8 from Williamson & Shmoys (WS)

Lecture 21 (Apr 28, 2022): Cuts and Metrics 3: Tree Embeddings
- Slides
- Video
- References: Chapter 8 from Williamson & Shmoys (WS)

Lecture 22 (Apr 29, 2022): Cuts and Metrics 4: Spreading Metrics
- Slides
- Video
- References: Chapter 8 from Williamson & Shmoys (WS)

Lecture 23 (May 06, 2022): 2-approximation for Steiner Tree via Metric Completion and EC-SNDP via Iterative Rounding
- Slides
- Video
- References: Chapter 11 from Williamson & Shmoys (WS)