Professor: Philip Klein (email available at directory.brown.edu, CIT 511), office hours by appointment
The following chapters will be emphasized
Topics are subject to change.
Problem sets will be assigned every 1 to 2 weeks. No exams will be given.
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).
In finding solutions to the problems in this class, you are allowed to collaborate with other students in the class. However, you should not retain any written (digitally or otherwise) record from your period of collaboration, and you should write up your solutions on your own, and list the names of those with whom you collaborated.
Please don't use sources other than the textbook and lectures in connection with doing the homework problems.
The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys.