(Announcement)
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.
Workshop Index
DIMACS Homepage
Contacting the Center
Next: Call for Participation