CMPUT675: Approximation Algorithms
Winter 2005, Wed and Fri 3:00-4:20:, in CSC B10.
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 efficiently that is
provably close to an optimal one is also acceptable.
This is the main goal of this course: find provably good approximation
solutions for the problems that are hard to solve exactly.
We study some of the common techniques in the design of
approximation algorithms. This is mostly done by studying some of
the well-known problems in the area.
We also talk about proving lower bounds, i.e. showing hardness of
approximation for several problems.
CMPUT304, plus strong undergraduate background in theoretical computer
science and mathematics. You must also have basic knowledge of graph
Approximation Algorithms, by Vijay Vazirani,
Springer-Verlag, Berlin, 2001.
You don't have to have the textbook since the lecture notes
will be available online, but it is a great book and
can be very helpful. You can buy the book from
Here is the course information sheet.
- Apr 18: Notes for the last two lectures are also posted.
- Apr 14: The deadline for assignment 3 has been extended
by exactly one week; it's now due Fri April 22, same time.
- Apr 7: Change to assignment 3: you only need
to do two of questions 4, 5, and 7.
- Mar 31: Assignment 3 has been posted. Note that there
will be an extra lecture on Monday April 4.
- Mar 29: New lecture notes have been posted.
- Mar 11: A typo in assignment 2 (q6) has been fixed (see below).
- Mar 07: Lecture notes for the last week are posted.
- Mar 05: Second draft of assignment 2 has been posted. Note that
question 3 has slightly changed.
- Feb 23: First draft of assignment 2 has been posted. More
problems will be added later on.
- Feb 13: A typo in question 5(c) of assignment 1 has been
corrected (see below).
- Jan 31: The (extra) lecture scheduled for Mon Feb 7 will
be in the same roome (CSC-B10).
- Jan 28: The extra lecture scheduled for Mon Jan 31st is
cancelled due to the conflict with the distinguished lecture series.
It will be held on Mon Feb 7 (location to be announced).
- Jan 20: Classroom changed!
from tomorrow, lectures will be held in CSC-B10.
- Jan 20: Assignment 1 has been posted. Some minor errors in
lecture notes 1 and 2 have been fixed (especially Theorem 2.8).
- Jan 17: As we agreed on Jan 12, we will have (longer)
Wed and Fri's (3:00-4:20) and no regular lectures on Mon instead. There
will be two extra lectures on Mon Jan 31st and Mon Apr 4.
- Jan 17: Please read Sections 12.1-12.2 of the text or
Sections 1-5 and 9
from the notes on linear programming by M. Goemans (see the links below).
- The first lecture will be on Jan 12.
- Lecture 1
Jan 12 (Introduction, definitions).
- Lecture 2,
Jan 14 (Vertex Cover, Set Cover greedy).
- Lecture 3,
Jan 19 (Linear programming, rounding for set cover).
- Lecture 4,
Jan 21 (Set cover primal dual).
- Lecture 5,
Jan 26 (metric Steiner tree and TSP).
- Lecture 6,
Feb 2 (Knapsack, Bin packing).
- Lecture 7,
Feb 4 (APTAS for bin packing).
- Lecture 8,
Feb 7 (Max-SAT, Derandomization using method of conditional prob).
- Lecture 9,
Feb 9 (Max-SAT randomized rounding).
- Lecture 10,
Feb 11 (Multiway cut and k-cut).
- Lecture 11,
Feb 16 (minimum multicut and multicommodity flows on trees).
- Lecture 12,
Feb 18 (multicut in general graphs).
- Lecture 13,
Mar 2 (approximation for packing Steiner trees undirected case).
- Lecture 14,
Mar 4 (approximation for packing Steiner trees directed case).
- Lecture 15,
Mar 9 (hardness of packing directed Steiner trees).
- Lecture 16,
Mar 11 (Steiner forests).
- Lecture 17,
Mar 16 (uncapacitated facility location problem).
- Lecture 18,
Mar 18 (Local search and k-Median).
- Lecture 19,
Mar 23 (Analysis of k-Median).
- Lecture 20,
(in pdf), Mar 30 (Introduction to
hardness of approximation).
- Lecture 21,
April 1 (PCP Theorem and hardness of Max-3SAT).
- Lecture 22,
April 4 (Improved PCP's).
- Lecture 23,
April 6 (Hardness of clique).
- Lecture 24,
April 8 (Hardness of clique, Label cover).
- Lecture 25,
April 13 (Parallel repetition, Hardness of set cover).
- Lecture 26,
April 15 (Hardness of Set Cover).
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.
- Assignment 3.
Due date is extended to April 22, 3:00pm.
Note that you can skip one of questions 4, 5, or 7.
- Assignment 2 second draft
( First draft).
In question 3, the approximation ratio is compared with OPT
(and not OPT*).
A typo in question 6 (definition of splittable) has been corrected.
- Assignment 1
Update Feb 13: For question 5(c), a typo has been corrected (it should
be (1-1/e+\eps) instead of (1-1/e-\eps)).
Update Feb 4: For question 6, you may use the fact that polynomial LP
solvers return a solution that is an extreme point.
There will be 3 assignment sets (for a total of 90%).
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, Vertex Cover
- Set Cover (Greedy algorithm, IP/LP-formulation and duality,
Randomized Rounding, Primal-dual)
- knapsack, Bin packing
- Randomized Rounding: MAX-SAT, Disjoint paths
- PTAS for Euclidean TSP
- Steiner trees and TSP: MST-based algorithms, Packing Steiner trees
- Facility location
- Multiway cut and k-cut
- Multicommodity flows and Multicuts
- Hardness results
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 ...
Here are some lecture notes by David P. Williamson.
- Notes on linear
algorithms, and randomized
algorithms from home page of
Michel X. Goemans ,
- Course notes by Joseph
- Notes from a few lectures on PCP by
Preliminary version of a book on
by Rajeev Motwani.
- 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.
- R. Motwani and P. Raghavan, Randomized algorithms, Cambridge
University Press, Cambridge, 1995.
A compendium of NP optimization problems , by Pierluigi Crescenzi
and Viggo Kann.