COMP.7100 Approximation Algorithms (Formerly 91.710)

Id: 036940 Credits: 3-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

Course prerequisites/corequisites are determined by the faculty and approved by the curriculum committees. Students are required to fulfill these requirements prior to enrollment. For courses offered through online or GPS delivery, students are responsible for confirming with the instructor or department that all enrollment requirements have been satisfied before registering.