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; 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 presentations.
  
• Due date for Assignment 2 has been extended until Oct 30 (at 11:00).
  
• Lecture notes 9 to 11 have been posted.
  
• I have added weight of each question to Assignment 2 (new version posted).
  
• 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 definitions.
• 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), Semidefinite Programming
  
• Lecture 11: Semidefinite Programming (cont'd)
• Lecture 12: Hardness of Approximation (introduction)
  
• Lecture 13: Improved PCP's
  
• Lecture 14: Hardness of Clique
  
• Lecture 15: Labelcover and 2P1R proof systems
• 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 Sadoddin)
• Lecture 19: Approximation algorithms for directed multicut (Tom Eastman)
• 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 Samadi)
  

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 and its source file.

Assignments:

• Homework Assignment 1: PS , PDF
• Homework Assignment 2: PS , PDF , Solutions
  
• Homework Assignment 3: PS , PDF

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

Tentative syllabus:

Approximation:

• 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, disjoint-paths)
• Polynomial Time Approximation Schemes (PTAS), knapsack, Bin packing
• Iterative rounding and SNDP and extensions
  
• Semidefinite programming, Max-Cut

• 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 lecture notes by David P. Williamson.
• Notes on linear programming, approximation algorithms, and randomized algorithms from home page of Michel X. Goemans ,
• 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 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.