DIMACS Workshop on Computing Approximate Solutions to NP-hard Problems


February 20 - 22,  2000
Princeton, NJ (Nassau Inn)

Sanjeev Arora, Princeton University, arora@cs.princeton.edu
Eva Tardos, Cornell University, eva@cs.cornell.edu
Luca Trevisan, Columbia University, luca@cs.columbia.edu

Presented under the auspices of the Special Year on Computational Intractability.

This workshop focuses on the design and analysis approximation algorithms, heuristics that compute solutions whose value  is provably within some fixed factor of the optimal. Although interest in approximation algorithms intensified in the 1970s soon after the   discovery of NP-completeness, the area has truly blossomed only in the past decade. Amazing progress has ocurred both in our ability to design approximation algorithms, and in proving limits to approximability. Approximation algorithms have been designed for many important problems such as balanced cut, network design, Euclidean TSP, facility location, and a number of scheduling problems. In the process, many simple and broadly-applicable techniques have emerged, such as rounding followed by dynamic programming, and more recently, the rounding of solutions obtained from linear or semi-definite relaxations, primal-dual  methods, geometric embeddings, and  the geometric divide-and-conquer approaches used for Euclidean TSP.

Also in the past decade, in an effort  to prove limits on approximability,  the notion of probabilistically checkable proof was invented in complexity theory to show that for some important problems such as clique, graph coloring and set cover, achieving a certain approximation ratio is no easier than solving the problem exactly.

The workshop will start with a set of plenary talks --geared to a broad audience-- surveying the current state of the art in this growing area. These will be followed by talks on recent results in approximation algorithms and lower bounds. We plan to leave enough free time during the workshop that the participants can discuss open problems, and make progress during the workshop.

The field of approximation algorithms has many open questions. A resolution of these questions would require new ideas in either  algorithm design or in proving  inapproximability. By simultaneously focussing on these complementary areas of research, we hope to foster further interactions between researchers working in them. The goal is to arrive at a better understanding of the limits of the known techniques in both areas and to focus attention on the main open problems.

The workshop will also examine practical aspects of approximation algorithms. We strongly believe that the same ideas that lead to provable worst case guarantees can give better quality solutions in practice than known heuristics. Indeed, existing implementations of approximation algorithms in most cases provide solution a lot closer to optimum than guaranteed by the worst case bound. Even better, in many cases the algorithm also provides very good lowerbounds on the optimum, thus allowing it  to prove that the solution found for the particular problem instance is quite close to optimum. These and other issues related to performance and implementation will be explored at the workshop.

The workshop will consist of a few invited presentations, each of them a 50-minute lecture, survey or tutorial. There will also be 30 minute talks on special issues. Limited support for participants is available to cover some expenses. Graduate students are particularly encouraged to participate.

 The workshop will be immediately followed by another workshop on "Faster algorithms for computing exact solutions to NP-hard problems," February 23-24, Princeton NJ.

Next: Call for Participation

Workshop Index

DIMACS Homepage

Contacting the Center
Document last modified on August 20, 1998.