CMPUT 675: Topics on Approximation Algorithms and Approximability
Fall 2007, Tue and Thr 11:00-12:20:, in ETL E1 018.
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 that is provably close to an optimal one is also acceptable. The next step is to show this is (almost) the best approximation one can hope for. These are the main goals of this course: find provably good approximation algorithms for the problems that are hard to solve exactly; and prove that finding better approximations are hard. We study some of the common and classical techniques in the design of approximation algorithms, followed by study of some more recent results in this field. Furthermore, we talk about the complexity of approximating these problems. This will be done by learning some classical and some more recent results on hardness of approximation.

CMPUT 304 or strong undergraduate background in theoretical computer science and mathematics. You must also have basic knowledge of graph theory.

There is no required text; lecture notes will be provided.
However Approximation Algorithms by Vijay Vazirani, Springer-Verlag, Berlin, 2001 will be helpful. Several topics covered will not be in the text.

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 and its source file.


Grading policy:
This is a theory course (no programming involved). There will be 3 assignments and you'll be required to a survey on a topic and present a paper on that topic.
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:


Hardness results: Surely, we won't have time to cover all these topics. Some other topics may be added as we go.

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