CMPUT 675: Approximation Algorithms
Winter 2022, Mon/Wed 12:30-13:50:, in VVC 2-227.
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, probability, and complexity.

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 5 take home 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:

Assignments:

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 , Ola Svensson
  
  

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