CMPUT675: Approximation Algorithms
Winter 2005, Wed and Fri 3:00-4:20:, in CSC B10.
Instructor: Mohammad R. Salavatipour

Most interesting optimization problems are NP-hard, and therefore it is unlikely that we can find optimal solutions for them efficiently. In many situations, finding a solution efficiently that is provably close to an optimal one is also acceptable. This is the main goal of this course: find provably good approximation solutions for the problems that are hard to solve exactly. We study some of the common techniques in the design of approximation algorithms. This is mostly done by studying some of the well-known problems in the area. We also talk about proving lower bounds, i.e. showing hardness of approximation for several problems.

CMPUT304, plus strong undergraduate background in theoretical computer science and mathematics. You must also have basic knowledge of graph theory.

Approximation Algorithms, by Vijay Vazirani, Springer-Verlag, Berlin, 2001.
You don't have to have the textbook since the lecture notes will be available online, but it is a great book and can be very helpful. You can buy the book from here .

Here is the course information sheet.

Lecture notes:

Template for course notes (modified from the one provided for CSC2401 offered by Micah Adler in 1998 in Univ. of Toronto). Here is a sample.


Grading policy:
There will be 3 assignment sets (for a total of 90%).

Also, each participant in the course is required to provide scribe notes for one or two weeks of lectures. This is worth 10% of your final mark. Scribe notes for each week are due the next Monday at noon. Scribe notes must be typed in LaTeX using the template provided above.

Tentative syllabus:

Useful Links:
Here are some useful links to more resources (books, course notes by other people who have taught this course, problems, etc.): Questions? Send email to me ...