This course is no longer offered
22915 Approximations of NP-Hard Problems
Credits: 4 graduate credits in Computer Science
Recommended: Linear Algebra I
The course is based on chapters 1-6, 8-13, 15, 17, and 18 from Approximation Algorithms, by V.V. Vazirani (Springer-Verlag, 2000).
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; Combinatorial algorithms – the greedy algorithm for the set cover problem, Steiner tree and TSP in metric space, multiway cut and k-cut, facility location problems, vertex cover, a pseudo-polynomial time algorithm for knapsack, scheduling; LP-based algorithms – introduction to LP-duality, linear programming for the set cover problem, the feasible dual approach, Steiner forests, multiway cut, sparsest cuts, balanced cuts and their applications.