CMPUT 675: Approximation Algorithms and Approximability
Winter 2018, Tue and Thr 11:00-12:20:, in CSC B41.
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. In this course we study design and analysis of Approximation Algorithms. These are efficient algorithms that find provably good approximation of the optimum solution. 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, but we will be using the following two books:

Grading policy:

This is a theory course (no programming involved). There will be 4 or 5 take home assignments. 
Also, each student might be asked to take notes for one or two lectures. The notes should be typeset using the template provided below. In doing so you have to complete the steps in the proofs and provided details for parts. This will be worth 10% of your grades. The other 90% of your grade will be based on your assignments.

Tentative topics (could change later):

Lecture notes:

As a template for course notes here is a sample and its source file.
Here is the algorithms.sty and picins.sty


Course Policies:

Please refer to the Department Course Policies for general information about course policies.

Assignments are due at the begining of the lecture on the due dates. Late assignments up to 24 hours will be deducted 20% of full grade. After 24 hours no assignment will be accepted.

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