Open Lecture — How Hard Is It To Find A Good Solution?

Suppose we are given an optimization problem where the quality of a proposed solution can be evaluated efficiently. Our natural instinct is to try find the best solution, but in some cases this requires infeasible amounts of computation. The study of when this happens leads to the classical theory of NP-completeness that was intitiated in the 1970s and mostly completed before 1990. The most famous NP-complete problem is the Traveling Salesman Problem.

When it is too computationally expensive to find the best solution one naturally turns to finding a "good" solution, which is often formalized as a solution that is within a small predetermined factor of optimal. Our understanding of this question has seen substantial progress in the last two decades.

It turns out that for some problems it is possible to find very good such approximate solutions quite efficiently, while in other cases even very weak approximation remains infeasible. The aim of this lecture is to give some highlight results of both of these types.

Light refreshments will be served before the lecture at 3:30 p.m.