CMPUT 675: Approximation
Algorithms and Approximability
Winter 2018, Tue and Thr 11:00-12:20:, in CSC B41.
Instructor: Mohammad
R. Salavatipour
Objectives:
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.
Prerequisites:
CMPUT 304 or strong undergraduate background in
theoretical computer science and mathematics. You must also have
basic knowledge of graph theory.
Textbook:
There is no required text, but we will be using
the following two books:
The Design of Approximation Algorithms by David Williamson and David Shmoys, Cambridge University Press, 2011
Approximation Algorithms by Vijay Vazirani, Springer-Verlag, Berlin, 2001.
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.
Lecture notes:
As a template for course notes here is a sample
and its source file.
Here is the algorithms.sty and picins.sty
Assignments:
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.
Here are some useful links to more resources (books, course notes by other people who have taught this course, problems, etc.):
Links to similar courses offered
by:
Chandra
Chekuri, Joseph
Cheriyan, Anupam
Gupta and R. Ravi, David
Williamson,
Notes on linear programming by Michel X. Goemans ,
Approximation Algorithms for NP-hard Problems. Dorit Hochbaum (Ed.), PWS Publishers, 1996. Below are links to some of the Chapters of this book that are available online: Hardness of Approximations by Sanjeev Arora and Carsten Lund, Cut Problems and their application to divide-and-conquer, by David Shmoys . All of these are part of the book "Approximation Algorithms for NP-hard problems" listed above. Copyrights for the material are held by PWS Publishing with all rights reserved.
Text on Computational Complexity:
Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern
Approach. (
homepage).
R. Motwani and P. Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995.
A compendium of NP optimization problems , by Pierluigi Crescenzi and Viggo Kann.
Questions? Send email to me ...