Call for Participation

                    THE SECOND DIMACS INTERNATIONAL
                  ALGORITHM IMPLEMENTATION CHALLENGE
            Clique, Graph Coloring, and Satisfiability


In conjunction with its Special Year on Combinatorial Optimization,
the Center for Discrete Mathematics and Theoretical Computer Science
(DIMACS) invites participation in an international Implementation
Challenge to find effective optimization and approximation algorithms
for the following NP-hard problems: Maximum Clique, Graph Coloring,
and Satisfiability.  The Implementation Challenge will take place
between September 1992 and August 1993.  Participants are invited to
carry out research projects related to these problem areas and to
present research papers at a DIMACS workshop to be held in Fall of
1993.  A refereed workshop proceedings will be published.


RESEARCH PROJECTS.  Recent results in complexity theory have shown
that, in a worst-case sense, the problems that are the subject of this
Challenge are not only hard to solve optimally, they are hard to
approximate.  Our goal in this Challenge is to provide an impetus for
a coordinated attack on the question of how hard they are in practice.
Participants may wish to implement algorithms for evaluation, to build
and study input generators, or to develop implementations for newer
architectures.  Projects may involve either public domain or
proprietary codes.  We are particularly interested in collecting
instances and instance generators for these problems, with the goal of
constructing a library of test problems that will be available for
study both during and after the challenge.


DIMACS SUPPORT.  DIMACS will provide benchmark instances for each
problem and support tools and guidelines for research projects.
DIMACS facilities will provide a clearing-house for exchange of
programs and input generators and for communication among researchers.
DIMACS can provide neither financial support for research projects nor
machine cycles for the experiments.


HOW TO PARTICIPATE.  For more information about participating in the
Implementation Challenge, send a request for the document "General
Information" (available September 15, 1992) to
                 challenge@dimacs.rutgers.edu.  
Request either LaTeX format (sent through email) or hard copy (sent
through U. S. Mail), and include your return address as appropriate.
Challenge materials will also be available via anonymous FTP from
DIMACS, and we expect most communication with respect to the Challenge
to take place over the Internet.


ADVISORY BOARD.  A committee of DIMACS members will provide general
direction for the Implementation Challenge.  Committee members are
Vasek Chvatal, Rutgers University, Bill Cook, Bell Communications
Research, David Johnson, AT\&T Bell Laboratories, Cathy McGeoch,
Amherst College, Bob Tarjan, Princeton University, and Michael Trick,
DIMACS Visiting Fellow/Carnegie Mellon University (Coordinator).