New Directions in Approximation Algorithms (2013)

Date & Time


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.

  • Participantsplus--large

    Sanjeev Arora Princeton University
    Boaz Barak Microsoft Research, New England
    Julia Chuzhoy Toyota Technological Institute at Chicago
    Uriel Feige Weizmann Institute
    Michel X. Goemans MIT
    Venkatesan Guruswami Carnegie Mellon University
    Johan Hastad KTH
    Sampath Kannan Simons Foundation
    Jonathan Kelner MIT
    Subhash Khot NYU/Chicago
    Monique Laurent Centrum Wiskunde & Informatica
    James Lee Washington University
    Laszlo Lovasz Eötvös Loránd University
    Yury Makarychev Toyota Technological Institute at Chicago
    Claire Matthieu ENS/Brown
    Assaf Naor NYU
    Shayan Oveis-Gharan Stanford University
    Prasad Raghavendra Georgia Tech
    David B. Shmoys Cornell University
    Mohit Singh MSR-Redmond
    David Steurer MSR-NERD/Cornell
    Ola Svensson EPFL
    Luca Trevisan Stanford University
    Anke Van Zuijlen MPI/William & Mary
Subscribe to MPS announcements and other foundation updates