New Directions in Approximation Algorithms (2013)

Organizers: Sanjeev Arora, Uriel Feige, Michel Goemans & David Shmoys

Many of the striking advances in theoretical computer science over the past two decades concern
 approximation algorithms, which compute provably near-optimal solutions to NP-hard optimization problems.
 Yet the approximability of several fundamental problems such as TSP, Graph Coloring, Graph Partitioning etc.
remains an open question. For other problems the so-called PCP Theorems and more recently, the Unique Games
Conjecture (UGC), provide a complexity-theoretic explanation for the failure to design better algorithms.

A quick succession of papers in the past 5 years or so has yielded new ideas for algorithmic approaches that show
promise of leading to a resolution of the classic open problems, as well as possibly a refutation of the UGC itself.
 These new approaches use structural insights gained from mathematical programming relaxations, either linear
programming (LP) or semidefinite programming (SDP). They draw upon a more complete arsenal of techniques
than had been seen earlier in math programming: Markov Chain Monte Carlo sampling, spectral techniques
(focusing especially on higher eigenvalues of the graph spectrum), high dimensional geometry, local vs global
geometric theorems, etc. Within the past year, approximation techniques have also been used to make progress on
semirandom complexity, which is an important — and largely nonunderstood — notion between worst-case and
average-case complexity.