|Meeting Time:||J: TTh 1:00-2:20|
|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).