22922 Approximation Algorithms

Credits: 4 graduate credits in Computer Science

Prerequisite: Admission to the graduate program in Computer Science 1

The course is based on The Design of Approximation Algorithms, by D.P. Williamson and D.B. Shmoys (Cambridge University Press, 2010) and on a study guide prepared by Niv Buchbinder and Zeev Nutov.

Many basic problems belong to the class of NP-hard problems. Finding an algorithm which runs within a reasonable period of time (in other words, the time polynomial in the input size) for one of these problems implies a polynomial algorithm for every NP-hard problem. Despite efforts over the last thirty years, no polynomial algorithm has been found for any NP-hard problem. The course deals with algorithms for finding an approximate solution in polynomial time for NP-hard problems. The common standard for measuring the quality of the approximation is the ratio between the value of the solution delivered by the algorithm and the optimal value, for the worst input. The course presents approximation algorithms for basic and important problems, such as the Traveling Salesperson Problem (TSP), scheduling problems, and network design problems (generalization of cuts, spanning trees). General methods for designing approximation algorithms (in other words, methods that work for a family of problems) are also discussed.

Topics: Introduction; Greedy algorithms and local search; Algorithms based on dynamic programming; Randomized algorithms based on rounding of linear programs; The primal-dual method and local search procedures; Cuts and rounding based on metrics; Deterministic rounding of linear programs.

---

1Students who have not fulfilled this requirement may, under certain circumstances, enroll in this course.