(Formerly CS251)

Approximation Algorithms

Course Home Page:
Meeting Time:J: TTh 1:00-2:20
Semester:2 (Spring)
Offered this year?No
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: None