CMPUT 675: Approximation
Algorithms and Approximability
Fall 2013, Tue and Thr 11:00-12:20:, in CSC B43.
Instructor: Mohammad
R. Salavatipour
Purpose:
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.
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.
Annoucnements:
Will be posted here.
Lecture notes:
Template for course notes Here is a sample (and in PDF) and its source file.
Assignments:
Grading policy:
This is a theory course (no programming involved). There will be 4
take home assignments; depending on the number of participants we
might have a course project which will be in the form of you
presenting one of the more recent (and significant) papers in the
area. I will suggest a number of topics for that.
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:
Covering problems (vertex cover, set cover)
Linear programming rounding (deterministic and randomized)
Primal-dual methods
Steiner tree, TSP, k-Center, k-median, facility location
Routing and Cut problems (multiway cut, k-cut, multicut)
Polynomial Time Approximation Schemes (PTAS)
Iterative rounding and SNDP and extensions
Semidefinite programming
metric methods, sparsest cut
PCP Theorem and hardness of approximation
Parallel repetition and labelcover, Hardness of set cover
Unique-Games Conjecture and consequences
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.):
Links to similar courses offered
by:
Moses
Charikar, Chandra
Chekuri, Joseph
Cheriyan, Anupam
Gupta and R. Ravi, Mohit
Singh, 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, Approximation Algorithms for Bin Packing: A Survey by E.G. Coffman, M.R. Garey, and D.S. Johnson , 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 ...