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])

References

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