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

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:

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.

Tentative topics (could change later):
• 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.

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

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.