CMPUT 675: Approximation Algorithms and Approximability
Fall 2013, Tue and Thr 11:00-12:20:, in CSC B43.
Instructor: Mohammad R. Salavatipour

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:

Annoucnements:

• Will be posted here.

Lecture notes:

• Lecture 1: Introduction, Vertex Cover, Steiner tree.
• Lecture 2 & 3: TSP, Set Cover, Introduction to LP, Set cover via rounding
• Lecture 4 & 5: Randomized rounding for Set Cover, LP duality, knapsack
• Lecture 6 & 7: Bin packing, Uncapacitated Facility location, k-center
• Lecture 8 & 9: local search for k-median, Steiner forest
• Lecture 10 & 11: Muliway cut, Multi-cut
• Lecture 12: (based on older notes) SDP rounding for Max-cut
• Lecture 13 & 14: (based on older notes) MST polytope via iterative method, bounded degree MST
• Lecture 15: bounded degree MST (cont'd)
• Lecture 16: (older notes) Survivable Network Desgin
• Lecture 17: (older notes) Approximating metrics by tree metrics
• Lecture 18: Group Steiner tree
• Lecture 19: Asymmetric k-Center
• Lecture 20: (older notes) PTAS for Euclidean TSP
• Lecture 21&22: (Older notes) Introduction to Hardness of Approximation, Improved PCP's

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

Assignments:

This is a theory course (no programming involved). There will be 4 take home assignments; depending on the number of participants we might have a course project which will be in the form of you presenting one of the more recent (and significant) papers in the area. I will suggest a number of topics for that.
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:

• Covering problems (vertex cover, set cover)

• Linear programming rounding (deterministic and randomized)

• Primal-dual methods

• Steiner tree, TSP, k-Center, k-median, facility location

• Routing and Cut problems (multiway cut, k-cut, multicut)

• Polynomial Time Approximation Schemes (PTAS)

• Iterative rounding and SNDP and extensions

• Semidefinite programming

• metric methods, sparsest cut

• PCP Theorem and hardness of approximation

• Parallel repetition and labelcover, Hardness of set cover

• Unique-Games Conjecture and consequences

Some other topics may be added as we go.