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:

• Inapproximability Results
  • Cases where finding good approximate solutions is as hard as finding optimal solutions
  • Proofs using the Probabilistically Checkable Proofs (PCP) Theorem
  • Advances in machinery for PCP
• New Hardness Results Based on Ingenious Reductions Starting from PCPs
  • Hardness results for basic routing, congestion, and related problems where there were previously no negative results
• Alternate Complexity Hypotheses Motivated by Recent Work
  • Unique Games Conjecture
  • Connection of unique games conjecture to Goemans-Williamson algorithm for Max Cut based on semidefinite programming
  • Relation to limitations of SDP-based approaches to variety of problems
  • Relation between SDP integrality gap constructions and hardness results based on the unique games conjecture
• Significant Strides in Approximation Algorithms
  • Key role of theory of finite metric spaces in advancing approximation algorithms toolkit
  • Connection to developments in geometric analysis
  • Characterization of ``typical'' inputs
• Connections between Complexity and Cryptography
  • Constructions of cryptographic primitives and their inverses
  • Lattice-based cryptography
  • Relations between cryptographic hardness and other areas such as game theory

Opportunities to Participate:

• Workshops: A variety of workshops and mini-workshops are being planned

• Working Groups: Interdisciplinary ``working groups'' will explore special forcus research topics.

• Tutorial: A tutorial will provide background knowledge to those who wish to participate in the special focus or just get an introduction to some of the fundamental issues in the field.

• Seminar Series: There will be a mix of research talks and practitioner presentations.

• Visitor Programs: Applications for research and graduate student visits to the center are invited. Some funds may be available for travel and local support.

• Graduate Student Support: Funds will be set aside for graduate students interested in attending workshops. Students interested in visiting DIMACS during the special focus are encouraged to apply to the special focus organizers.

• Publications: We anticipate that a variety of publications, including AMS-DIMACS volumes, technical reports, abstracts and notes on the WWW, and DIMACS modules will result from the special focus.

Index of Special Focus on Hardness of Approximation

DIMACS Homepage