Approximation Algorithms

Catalog description

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 1510 , 1550 , 1810 , 1950J , 1950L, any graduate-level course on algorithms (including 2500A , 2500B , 2580 ).