APPROXIMATION ALGORITHMS

Course Description

So, you’re faced with a difficult real world algorithm problem and you’ve shown that the standard techniques won’t work. Maybe you’ve proven that it’s NP-Hard, so what next? You could write some brute force code hoping that it terminates as your resource usage skyrockets. Maybe you can solve an easier version that works for your use case. Or, you could look into approximate solutions that are easy to implement and guarantee answers which are “good enough.” In this course, we’ll see that a variety of natural problems are notoriously hard to solve exactly, but admit beautifully simple (and some not so simple!) approximation algorithms.

While this course can be seen as a natural extension of CS 130A/130B, I do not expect you to have taken those. As such, we will start with a brief introduction to models of computation and formally introduce P vs NP. We will then prove NP-hardness and derive approximation algorithms for a variety of optimization problems including vertex cover, (metric) traveling salesman problem, variants of independent set, max cut, etc. Other topics include polynomial time approximations schemes (PTAS), hardness of approximation, approximation preserving reductions, and the unique games conjecture.

Why take this course?
* You will get to solve many algorithmic problems, often working with your peers
* You will get an intuition for how to spot hard problems, and know what to do when you face one at your next job
* You will get an answer to “What does research in computer science theory look like?”