2008-2011 Special Focus on Hardness of Approximation: Overview

Computational intractability is a fundamental theme in discrete mathematics and theoretical computer science. Approximation algorithms offer an important strategy for attacking computationally intractable problems, and approximation algorithms with performance guarantees have been designed for a host of important problems such as balanced cut, network design, Euclidean TSP, facility location, and machine scheduling. Many simple and broadly-applicable approximation techniques have emerged for some provably hard problems, while in other cases, inapproximability results demonstrate that achieving a suitably good approximate solution is no easier than finding an optimal one. The ongoing study of approximation and inapproximability has led to the discovery of surprising connections and deep mathematical results, including the celebrated probabilistically checkable proofs (PCP) theorem and the unique games conjecture and its implications.

Research has yielded some theoretical limits on approximability, including hardness results for problems based on different kinds of complexity assumptions, integrality gap constructions showing limitations for linear programming (LP) and semidefinite programming (SDP) approaches, as well as limitations on lift-and-project systems for strengthened LP and SDP relaxations. Important recent results, such as the unique games conjecture, are based on alternate complexity hypotheses and suggest a number of fascinating, but not well-understood, hardness results. Among these are the apparent connections between SDP integrality gap constructions and hardness results based on the unique games conjecture and the observation that the optimality of the SDP-based Goemans-Williamson algorithm for the MAX CUT problem implied by the unique games conjecture seems to capture the limitations of SDP-based approaches for a variety of problems. These observations and connections are tantalizing, but remain incompletely understood.

This special focus is spurred by these recent exciting developments and our feeling that focusing the attention of the community on them at this time can lead to dramatic new developments. The special focus will bring together a large number of researchers to highlight many of the new and exciting developments surrounding approximability and inapproximability and their implications and to draw attention to several important open problems and sharpen the general understanding of what makes problems hard to solve. It will draw on the strong DIMACS community working in discrete mathematics and theoretical computer science, but will also attract key researchers from across the country and internationally, and it will emphasize the involvement of students and early-career researchers.

Primary goals of the new Special Focus on Hardness of Approximation are to disseminate current research, to lay out a research agenda for the future, to develop new relationships between researchers, and to begin to make progress on the future research agenda.

The Themes of the Special Focus Include:

Opportunities to Participate:

Up. Index of Special Focus on Hardness of Approximation
DIMACS Homepage
Contacting the Center
Document last modified on December 3, 2009.