Abstract:

Many fundamental combinatorial properties, such as e.g. clique number, chromatic number, or maximum cut of a graph, are NP-hard to compute exactly. But what happens if the problems are slightly relaxed, and one instead asks for approximate computations of these properties? It turns out that different problems behave very differently. For instance, the clique number and chromatic number turn out to be NP-hard to approximate even within an almost linear factor, whereas there is a trivial algorithm which finds a factor two approximation for the maximum cut.

In recent years, the so-called Unique Games Conjecture has become an important tool for obtaining strong hardness of approximation results, and there are now many problems for which the best possible approximation ratio is known, assuming this conjecture. We discuss some of these consequences and, time permitting, give a high-level overview of how they are proved.

No prior knowledge of approximation algorithms is needed.