CMPUT 675: Approximation Algorithms and Approximability
Winter 2018, Tue and Thr 11:00-12:20:, in CSC B41.
Instructor: Mohammad R. Salavatipour

Objectives:

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. In this course we study design and analysis of Approximation Algorithms. These are efficient algorithms that find provably good approximation of the optimum solution. 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.

Grading policy:

This is a theory course (no programming involved). There will be 4 or 5 take home assignments. 
Also, each student might be asked to take notes for one or two lectures. The notes should be typeset using the template provided below. In doing so you have to complete the steps in the proofs and provided details for parts. This will be worth 10% of your grades. The other 90% of your grade will be based on your assignments.

• Design Techniques:
• Greedy and combinatorial methods,
  
• Dynamic programming and sclaing,
• Local search
• random sampling
  
• Linear programming (deterministic rounding, randomized rounding, primal-dual, iterative rounding)
• semi-definite programming and rounding
• metric embeddings
  
  
• Problems to discuss:
• Vertex Cover, Steiner tree. Set Cover
  
• TSP (symmetric and other variants)
• knapsack, bin packing
• Scheduling problems
• Facility location, k-median, k-center
  
• Steiner forest, Steiner network
• k-cut, multi-way cut, multi-cut, sparsest cut
  
• max-cut, max-sat
• Hardness of approximation (Intro to PCP, simple proofs, improved PCP's).
  

Lecture notes:

• Week 1: Introduction, Vertex Cover, Steiner tree, TSP, Set Cover (old Notes)
  Relevant sections from Vazirani: 1, 2; WS: 2.4
  
  
• Lecture 3: Introduction to LP, Set Cover via LP rounding (old Notes)
  Sections from Vazirani: 14.2, 14.3; WS: 1.2-1.7
  
  
• Lecture 4: FPTAS for Knapsack, Bin Packing (old Notes)
  Sections from Vazirani: 8; WS: 3.1
  
  
• Lecture 5: Bin Packing, Max-SAT (Notes from 2011 and  Notes from 2015)
  Sections from Vazirani: 9, 16.1-16.2; WS: 3.3, 5.1-5.3
  
  
• Lecture 6: Max-SAT, dual LP (see notes from last lecture, plus Section 4.2 from this)
  Sections from Vazirani: 16.3, 16.4, 12; WS: 5.4, 5.5
  
  
• Lecture 7: Uncapacitated Facility Location via LP, k-centre (see these notes)
  Sections from WS: 5.8, 2.2
  
  
• Lecture 8: k-Median via local search (see these notes here)
  Sections 9.2 from WS. Also this.
  
  
• Lecture 9: Steiner forest, primal-dual method (older notes)
  Section 22 from Vazirani; WS section 7.4
  
  
• Lecture 10: UFL via primal dual
  Section 24 from Vazirani; 7.6 from WS.
  
  
• Lecture 11: Lagrangian relaxation (k-Median)
  Section 25 from Vazirani; 7.7 from WS.
  
  
• Lecture 12: minimizing makespan on parallel machines
  Section 17 from Vazirani,
  
  
• Lecture 13: Generalized Assignment, Integer Multi-commodity flow.
  Section 5.10, 5.11, 11.1 from WS
  
  
• Lecture 14: PTAS for Euclidean TSP
  Section 11 from Vazirani; 10.1 from WS.
  
  
• Lecture 15: Cut problems (k-cut, multi-way cut)
  Chapter 4, 15 from Vazirani; 8.1,8.2 from WS.
  
  
• Lecture 16: Multiway cut via randomized rounding (older notes).
  Chapter 4, 15 from Vazirani; 8.1,8.2 from WS.
  
  
• Lecture 17: Multicut via region growing (see notes for Lecture 16).
  Chapter 20 from Vaziran; 8.3 from WS.
  
  
• Lecture 18: Approximating metrics with tree metrics (older notes)
  Chapter 8.5 from WS.
  
  
• Lecture 19: Group Steiner tree.
  See also this paper and this.
  
  
• Lecture 20: Steiner network and iterative rounding (older notes)
  Chapter 23 from Vazirani; 11.3 from WS
  
  
• Lecture 21: Finish Steiner network, Start semi-definite programming
  Chapter 23 and 26 from Vazirani; 11.3 and  6.1-6.2 from WS. (older notes)
  
  
• Lecture 22: Finish semi-definite programming for Max-Cut, Max-2SAT
  
  
• Lecture 23: Introduction to hardness of approximation (older notes)
  Chapter 29.1-3 from Vazirani; 16.1-3 from WS.
  
  
• Lecture 24: Improved PCP's, Hastad's Theorem (see above notes).
  
  
• Lecture 25: Label Cover (older notes)
  Chapter 29 from Vazirani
  
  
  

As a template for course notes here is a sample and its source file.
Here is the algorithms.sty and picins.sty

Assignments:

• Homework Assignment 1.  Solutions sketch for most question.
  
• Homework Assignment 2. (due date Feb 27) Solutions sketch
  
• Homework Assignment 3.
• Homework Assignmenr 4.
  

Course Policies:

Please refer to the Department Course Policies for general information about course policies.

Assignments are due at the begining of the lecture on the due dates. Late assignments up to 24 hours will be deducted 20% of full grade. After 24 hours no assignment will be accepted.

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:
  Chandra Chekuri, Joseph Cheriyan, Anupam Gupta and R. Ravi, David Williamson,
  
  

•  Iterative Methods in Combinatorial Optimization, by L. Lau, R. Ravi, and M. Singh.
  

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