The theory of NP-completeness is one of the cornerstones of complexity theory in theoretical computer science. Approximation algorithms offer an important strategy for attacking computationally intractable problems, and approximation algorithms with performance guarantees have been designed for a host of important problems such as balanced cut, network design, Euclidean TSP, facility location, and machine scheduling. Many simple and broadly-applicable approximation techniques have emerged for some provably hard problems, while in other cases, inapproximability results demonstrate that achieving a suitably good approximate solution is no easier than finding an optimal one. The celebrated PCP theorem established that several fundamental optimization problems are not only hard to solve exactly but also hard to approximate. This work shows that a broad class of problems is very unlikely to have constant factor approximations, and in effect, establishes a threshold for such problems such that approximation beyond this threshold would imply P= NP. More recently, the unique games conjecture of Khot has emerged as a powerful hypothesis that has served as the basis for a variety of optimal inapproximability results.
This tutorial targets graduate students and others who are new to the field. It will aim to give participants a general overview of approximability, introduce them to important results in inapproximability, such as the PCP theorem and the unique games conjecture, and illustrate connections with mathematical programming techniques.
List of speakers:
Next: Call for Participation
Workshop Index
DIMACS Homepage