[Lowerbounds, Upperbounds]

Why NP got a new definition: the quest to understand the approximation properties of NP-hard optimization problems

Sanjeev Arora
Princeton University

Friday, January 27, 2006
10:30am - SENSQ 5317

Abstract

Thousands of optimization problems in a variety of application areas are known to be NP-hard. Since no efficient exact algorithm is known, researchers have tried to understand the complexity of computing approximately optimal solutions. Surprisingly, NP-complete problems differ a lot in this respect. This talk is a survey of the many exciting results proved in the last 15 years in the quest to understand this phenomenon.

The first type of result shows nonapproximability: for many problems, computing approximate solutions is no easier than computing optimal solutions. This is shown by proving a new probabilistic characterization of NP, according to which it is possible to check certificates for membership in an NP language by examining a constant number of bits in the certificate. We will survey this result (the so-called PCP Theorem) and its many extensions.

The other type of result consists of designing better approximation algorithms. This endeavor has also been successful for many problems, and a large body of techniques has been developed in the past decade. We will survey some of these.

The talk will be self-contained.