CMPUT 675 - Approximation Algorithms and Approximability

Overview

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.

Topics

• Greedy algorithms
• Scaling + dynamic programming techniques
• Local search techniques
• Linear programming, duality, and extreme point analysis
• Semidefinite programming
• The PCP theorem and hardness of approximation

Course Work

• Assignments
• Scribe notes
• Final project