(Formerly CS251)

Approximation Algorithms

Course Home Page:
Location:CIT 477
Meeting Time:D: MWF 11:00-11:50
Exam Group:04: 11-MAY-2018 Exam Time: 02:00:00 PM
Offered this year?Yes
When Offered?Most years


Approximation algorithms deal with NP-hard combinatorial optimization problems by efficiently constructing a suboptimal solution with some specified quality guarantees. We study techniques such as linear programming and semidefinite programming relaxations, and apply them to problems such as facility location, scheduling, bin packing, maximum satifiability or vertex cover. Prerequisite: one of the following: CSCI 1570 or any graduate-level course on algorithms (including 2500A, 2500B, 2580).

CRN: 25770