Id: 036940
Credits Min: 3
Credits Max: 3
Description
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.
Prerequisites
Pre-Req: 91.503 Algorithms.
View Current Offerings