CSCI2510: Approximation Algorithms (Spring 2015)




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.

Calendar, subject to change


Tutorial on sum-of-squares method


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).

Collaboration Policy

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.

While the internet may be used to find other applications and analyses of techniques, do not look at solutions to the homework problems.


The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys.