From: trick@shakespeare.rutgers.edu (Mike Trick)
Newsgroups: sci.math
Subject: DIMACS Implementation Challenge (LaTeX Version)
Summary: Announcement of the DIMACS Implementation Challenge (LaTeX version)
Keywords: implementation challenge clique coloring satisfiability
Date: 29 Sep 92 18:20:10 GMT
Organization: Rutgers Univ., New Brunswick, N.J.

% This is the LaTeX version of the Call for Participation for
% the Second DIMACS Implementation Challenge on Cliques, Coloring
% and Satisfiability.  Please post and distribute widely!
%
%                               Michael Trick
%                               Challenge Coordinator
%
\documentstyle[11pt]{article}
\pagestyle{empty}
\setlength{\topmargin}{-.8in}
\addtolength{\textheight}{1.8in}
\addtolength{\textwidth}{\evensidemargin}
\addtolength{\textwidth}{\oddsidemargin}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\addtolength{\textwidth}{-1.0\oddsidemargin}
\addtolength{\textwidth}{-1.0\evensidemargin}
\begin{document}

\begin{center}
{\Large  Call for Participation}\\ 
{\LARGE \bf The Second DIMACS International \\
Algorithm Implementation Challenge:\\
Clique, Graph Coloring, and Satisfiability\\ }
\end{center} 

\setlength{\baselineskip}{14pt}

\vspace{.25in}

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: {\bf Maximum Clique}, {\bf Graph Coloring},
and {\bf 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.

\paragraph{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.

\paragraph{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.  

\paragraph{How to Participate} 

For more information about participating in the Implementation
Challenge, send a request for the document {\em General Information}
(available September 15, 1992) to {\bf 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.

\paragraph{Advisory Board.}  
A committee of DIMACS members will
provide general direction for the Implementation Challenge.
Committee members are
Va\v{s}ek Chv\'atal, 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).

\end{document}
Newsgroups: sci.math,comp.theory