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 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.

Prerequisites:
CMPUT304, plus strong undergraduate background in theoretical computer science and mathematics. You must also have basic knowledge of graph theory.

Textbook:
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 .

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) lectures on 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 (in pdf), Jan 12 (Introduction, definitions).
• Lecture 2, (in pdf), Jan 14 (Vertex Cover, Set Cover greedy).
• Lecture 3, (in pdf), Jan 19 (Linear programming, rounding for set cover).
• Lecture 4, (in pdf), Jan 21 (Set cover primal dual).
• Lecture 5, (in pdf), Jan 26 (metric Steiner tree and TSP).
• Lecture 6, (in pdf), Feb 2 (Knapsack, Bin packing).
• Lecture 7, (in pdf), Feb 4 (APTAS for bin packing).
• Lecture 8, (in pdf), Feb 7 (Max-SAT, Derandomization using method of conditional prob).
• Lecture 9, (in pdf), Feb 9 (Max-SAT randomized rounding).
• Lecture 10, (in pdf), Feb 11 (Multiway cut and k-cut).
• Lecture 11, (in pdf), Feb 16 (minimum multicut and multicommodity flows on trees).
• Lecture 12, (in pdf), Feb 18 (multicut in general graphs).
• Lecture 13, (in pdf), Mar 2 (approximation for packing Steiner trees undirected case).
• Lecture 14, (in pdf), Mar 4 (approximation for packing Steiner trees directed case).
• Lecture 15, (in pdf), Mar 9 (hardness of packing directed Steiner trees).
• Lecture 16, (in pdf), Mar 11 (Steiner forests).
• Lecture 17, (in pdf), Mar 16 (uncapacitated facility location problem).
• Lecture 18, (in pdf), Mar 18 (Local search and k-Median).
• Lecture 19, (in pdf), Mar 23 (Analysis of k-Median).
• Lecture 20, (in pdf), Mar 30 (Introduction to hardness of approximation).
• Lecture 21, (in pdf), April 1 (PCP Theorem and hardness of Max-3SAT).
• Lecture 22, (in pdf), April 4 (Improved PCP's).
• Lecture 23, (in pdf), April 6 (Hardness of clique).
• Lecture 24, (in pdf), April 8 (Hardness of clique, Label cover).
• Lecture 25, (in pdf), April 13 (Parallel repetition, Hardness of set cover).
• Lecture 26, (in pdf), 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.

Assignments:

• 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.

Grading policy:
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.

Tentative syllabus:

• 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 lecture notes by David P. Williamson.
• Notes on linear programming, approximation algorithms, and randomized algorithms from home page of Michel X. Goemans ,
• Course notes by Joseph Cheriyan.
• Notes from a few lectures on PCP by Madhu Sudan.
• Preliminary version of a book on Approximation Algorithms 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.