91.710 Approximation Algorithms

Approximation Algorithms

Course Details
Min Credits 3
Max Credits 3
Course ID 36940
Status Active

This course covers advanced topics in approximation algorithms for NP-hard problems, including combinatorial algorithms and LP-based algorithms for set cover, k-cut, k-center, feedback vertex set, shortest superstring, knapsack, bin packing, maximum satisfiability, scheduling, Steiner tree, Steiner Forest, Steiner network, facility location, k-median, semidefinite programming. It also covers counting problems, shortest vector, hardness of approximation, and open problems for research.

Pre/Co-Requisites: Pre-Req: 91.503 Algorithms.