CSCI2510: Approximation Algorithms (Spring 2015)

Announcements

Staff

Topics

The following chapters will be emphasized
Topics are subject to change.

Assignments

Problem sets will be assigned every 1 to 2 weeks. No exams will be given.

Calendar, subject to change

Resources

Tutorial on sum-of-squares method

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

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.

Textbook

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