Approximation Algorithms (B.Stat, 2023-24)

Instructor  Arijit Ghosh

Description To study the basics of Approximation Algorithms. This is the final module of the course Design and Analysis of Algorithms (B.Stat 2023-24) taught by Krishnendu Mukhopadhyaya.

Syllabus

• Hitting Set and Set Cover problems

• Standard NP-complete problems in graph theory

  • • Independent Set 

    • Dominating Set

    • Vertex Cover 

    • Travelling Salesman Problem and Metric Travelling Salesman Problem

• Introduction to Linear Programming and Integer Linear Programming

References

• [V03] V. Vazirani, Approximation Algorithms, Springer, 2003

• [MG07] J. Matoušek and B. Gärtner, Understanding and Using Linear Programming, 2007

Lecture details

Topics covered in Lecture 1

• Hitting Set and Set Cover problems

• Standard NP-complete problems in graph theory

  • • Independent Set 

    • Dominating Set

    • Vertex Cover 

    • Travelling Salesman

• Greedy methods

  • • O(log n)-approximation for Set Cover problem

    • 2-approximation for Vertex Cover problem via maximal matching 

• Basics of Linear Programming (LP) and Integer Linear Programming (ILP)

• Reading materials:

  • • Chapters 1 and 2 from [V03]

    • Lecture 2 from Ola Svensson's course on Approximation Algorithms and Hardness of Approximation at EPFL

    • Chapters 1 and 3 from [MG07]

Topics covered in Lecture 2

• ILP formulation of vertex cover, and its fractional relaxation

• Extreme point structure of fractional vertex cover problem

• Slightly better than 2-approximation for vertex cover problem 

• Introduction to Metric Travelling Salesman Problem (MTSP) and 2-approximation via Minimum Spanning Tree

• 3/2-approximation for MTSP

• Reading materials:

  • • Chapter 3 from [V03]

    • Lecture 6 from Ola Svensson's course on Approximation Algorithms and Hardness of Approximation at EPFL