CMPUT 675: Approximation Algorithms and Approximability
Fall 2015, Tue and Thr 2:00-3:20:, in CSC B43.

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, but we will be using the following two books:

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, Set Cover, Steiner Tree, TSP.
• Lecture 3: Introduction to LP, Set Cover via LP rounding,
• Lecture 4: Set Cover via Randomized rounding, Knapsack, Bin packing
• Lecture 5: Bin packing, Max SAT
• Lecture 6: Max SAT, Facility Location
• Lecture 7 & 8: Facility Location, K-Center, K-Median
• Lecture 9: Primal-Dual, Steiner Forest
• Lecture 10: Multiway Cut
• Lecture 11 & 12: Multiway cut, Multicut
• Lecture 13: Generalized Assignment Problem, MST polytope
• Lecture 14 (older notes): MST polytope, Min-cost Bounded Degree Spanning tree
• Lecture 15 & 16: Iterative Rounding (Min-cost Bounded degree Spanning tree, Survivable Network Design)
• Lecture 17 & 18: Semidefinite programing (Max-cut, Max-2SAT), Metric embeddings
• Lecture 19 & 20: Approximation of metrics by tree metrics (older notes), PTAS for Euclidean TSP (older notes)
• Lecture 20 & 21: Intro. to Hardness of approximation, PCP (Older notes)
• Lecture 22 & 23: Label Cover, Hardness of Set cover (older notes)

Template for course notes Here is a sample (and in PDF) and its source file.
Here is the algorithms.sty

Assignments: