Approximation Hardness and the Unique Games Conjecture

The theory of NP-completeness suggests that some problems in CS are inherently hard—that is, there is likely no possible algorithm that can efficiently solve them. Unfortunately, many of these problems are ones that people in the real world genuinely want to solve! How depressing! What can one do when faced with a real-life industrial optimization problem whose solution may save millions of dollars but is probably impossible to determine without trillions of years of computation time?

One strategy is to be content with an approximate (but provably "almost ideal") solution, and from here arises the theory of approximation algorithms. However, this theory also has a depressing side, as many well-known optimization problems have been shown to be provably hard to approximate well.

This talk shall focus on the depressing. We will prove that various optimization problems (such as traveling salesman and max directed disjoint paths) are impossible to approximate well unless P=NP. These proofs are easy to understand and are REALLY COOL thanks to their use of very slick reductions.

We shall explore many NP-hard optimization problems and state the performance of the best known approximation algorithms and best known hardness results. Tons of open problems will be mentioned, including the unique games conjecture, which, if proven true, implies the optimality of many of the best known approximation algorithms for NP-complete problems like MAX-CUT and INDEPENDENT SET.

I promise fun times and no gruesome math. Basic knowledge of graph theory and computational complexity might help but is not required.