Approximation Algorithms

Topics Covered

• Lecture 1: Introduction to Approximation Algorithms (Chapter 1 of [VV])
• Lecture 2: Vertex Cover Problem (Chapter 1 of [VV])
• Lecture 3: Steiner Tree Problem (Chapter 3 of [VV])
• Lecture 4: Metric Traveling Salesman Problem (Chapter 3 of [VV])
• Lecture 5: k-Centre Problem (Section 5.1 of [VV])
• Lecture 6: Makespan Scheduling (Section 10.1 of [VV])
• Lecture 7: Knapsack Problem (Chapter 8 of [VV])
• Lecture 8: Linear Programming for Approximaton Algorithms
• Lecture 9: Set Cover: Randomized Rounding (Section 14.2 of [VV])
• Lecture 10: Set Cover: Integrality Gap Lower Bound

References

• Approximation Algorithms by Vijay V. Vazirani [VV].
• The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys [WS].