CMPUT 675: Approximation
Algorithms
Fall 2011, Tue and Thr 2:00-3:20:, in CSC
B41.
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:
Oct 5: Just noticed that page numbers referenced in the assignment are different in the hard copy and electronic copy of the book. The exercise numbers are the same though.
Lecture notes:
Lecture 1 , Sept 8, 2011 (Introduction, Vertex Cover).
Lecture 2 and 3, Sept 13 and 15, 2011 (Set Cover, Introduction to LP).
Lecture 4 and 5, Sept 20 and 22, 2011 (Set Cover via LP, Knapsack)
Lecture 6 and 7, Sept 27 and 29, 2011 (Bin Packing, Max-Sat)
Lecture 8 and 9, Oct 4 and 6, 2011 (Facility Location via LP, k-Center, k-Median, Steiner Forest)
Lecture 10 and 11, Oct 11 and 13, 2011 (Iterative rounding, Survivable Network design)
Lecture 12 and 13, Oct 18 and 20, 2011 (MST polytope via iterative method, Bounded degree MST)
Lecture 14 (Multiway cut) and Lecture 15 (Multicut) from an older course.
Lecture 16 Nov 1, 2011 (Approximating using tree metrics) and Lecture 17 Nov 3, 2011 (SDP rounding, Max-Cut from an older course)
Lecture 18 Nov 8, 2011, PTAS for
Euclidean TSP (Unedited!).
Lecture 19 and 20 Nov 15 and 17,
2011 (Introduction to hardness of approximation, Improved
PCP's) from older notes.
Here are the
lecture noes on limits of of approximation (PCP and unique
Games)
Template for course notes Here is a sample (and in PDF) and its source file.
Assignments:
Assignment 1 in PDF due Oct 18 (note that the page numbers in the electronic version of SW are different).
Assignment 2 in PDF due Nov 15.
Assignment 3 in PDF due Dec 8.
Grading policy:
This is a theory course (no programming involved). There will be
3 or 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, disjoint-paths)
Polynomial Time Approximation Schemes (PTAS), knapsack, Bin packing
Iterative rounding and SNDP and extensions
Semidefinite programming, Max-Cut
metric methods, sparsest cut
PCP Theorem and hardness of Max-3SAT
Parallel repetition and labelcover, Hardness of set cover
Unique-Games Conjecture and consequences
Surely, we won't have time to cover all these topics. 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 ...