CMPUT 675: Topics on Approximation
Fall 2007, Tue and Thr 11:00-12:20:, in ETL E1 018.
Instructor: Mohammad R.
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
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
CMPUT 304 or strong undergraduate background in theoretical computer
science and mathematics. You must also have basic knowledge of graph
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.
- Solutions to A2 have been posted below.
- Assignment 3 is posted.
- Lecture notes from 12 to 16 are posted as well as the schedule of
- Due date for Assignment 2 has been extended until Oct 30 (at
- Lecture notes 9 to 11 have been posted.
- I have added weight of each question to Assignment 2 (new version
- Assignment 2 is posted.
- Lectures 5 to 8 are posted.
- Assignment 1 is posted below.
Here you can find a list of potential
project topics with some references. For each topic, you are expected
to present an overview of the previous results plus the most recent
result on that topic. You can propose your own topic too. In either
case, please contact me before deciding on what and how much to read.
In general, the hardness of approximation results might be more
difficult to read.
- Lecture notes 3 has been posted.
- Lecture notes 1 and 2 have been posted.
- Lecture 1: Introduction, Basic
- Lecture 2: Vertex Cover, Set Cover, LP
- Lecture 3: Rounding for Set Cover,
(weighted) VC, Integrality gap
- Lecture 4: Priaml/Dual (Set Cover), TSP
- Lecture 5: FPTAS for knapsack, Max-SAT
- Lecture 6: Steiner tree, Steiner forest
- Lecture 7: Steiner forest, Multicut
- Lecture 8: Multicut (continued)
- Lecture 9: Steiner Network
- Lecture 10: Steiner Network (cont'd),
- Lecture 11: Semidefinite Programming
- Lecture 12: Hardness of Approximation
- Lecture 13: Improved PCP's
- Lecture 14: Hardness of Clique
- Lecture 15: Labelcover and 2P1R proof
- Lecture 16: Hardness of Set Cover
- Lecture 17: Bounded degree spanning trees (Babak Behsaz)
- Lecture 18: Prize Collecting Steiner Trees (Pirooz Chubak)
- Lecture 17: Approximation algorithms for Buy-at-Bulk (Reza
- Lecture 19: Approximation algorithms for directed multicut (Tom
- Lecture 20: Hardness of Asymmetirc k-center (Zac Friggstad)
- Lecture 21: Hardness of edge-disjoint paths (Carsten Moldenhauer)
- Lecture 22: Approximation algorithms for k-Median (Yi Shi)
- Lecture 23: Expander flows, geometric embeddings, and graph
partitionings (Amin Jorati)
- Lecture 24: Facility Location Problem (Jiaofen Xu)
- Lecture 25: The complexity of 2-Player Nash-Equilibrium (Mehdi
Template for course notes (modified
from the one provided for CSC2401 offered by Micah Adler in 1998 in
of Toronto). Here is a sample and its source file.
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.
- Preliminaries, basic definitions,
- Covering problems (vertex cover, set cover)
- Linear programming rounding and Primal-dual
- Steiner tree, TSP, k-Center, k-median
- Routing and Cut problems (multiway cut, k-cut, multicut,
- Polynomial Time Approximation Schemes (PTAS), knapsack, Bin
- Iterative rounding and SNDP and extensions
- Semidefinite programming, Max-Cut
Surely, we won't have time to cover all these topics. Some other topics
may be added as we go.
- PCP Theorem and hardness of Max-3SAT
- Parallel repetition and labelcover, Hardness of set cover
- Edge Disjoint Paths, cost-distance network
- Hypergraph vertex cover and asymmetric p-center
- Unique-Games Conjecture and consequences
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 ...
are some lecture notes by David P. Williamson.
- Notes on linear
algorithms, and randomized
algorithms from home page of Michel X.
- Notes for similar courses by Joseph
Cheriyan (at Waterloo), Chandra
Chekuri (at UIUC), Moses
Charikar (at Princeton), Gupta
and Ravi (at CMU).
- Approximation Algorithms for NP-hard Problems. Dorit Hochbaum
(Ed.), PWS Publishers, 1996. Below are links to some of the Chapters of
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.
- R. Motwani and P. Raghavan, Randomized algorithms,
Cambridge University Press, Cambridge, 1995.
compendium of NP optimization problems , by Pierluigi Crescenzi
and Viggo Kann.