\documentstyle[12pt]{article}
\setlength{\topmargin}{-.5in}
\addtolength{\textheight}{1.5in}
\addtolength{\textwidth}{\evensidemargin}
\addtolength{\textwidth}{\oddsidemargin}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\addtolength{\textwidth}{-1.0\oddsidemargin}
\addtolength{\textwidth}{-1.0\evensidemargin}
\begin{document}
\setlength{\baselineskip}{20pt}
\newcommand{\comment}[1]{}

\title{
The Third DIMACS International \\ 
Algorithm Implementation Challenge: \\
General Information 
}
\author{ } 

\maketitle 

\noindent {\it This document provides a general overview of the
organization of the Challenge.}

\section{Introduction}

In conjunction with its Special Year on Parallel Computing, the Center
for Discrete Mathematics and Theoretical Computer Science (DIMACS)
invites participation in an international Implementation Challenge to
study effective parallel algorithms for combinatorial problems.
Participants are invited to carry out research projects related to the
problem areas specified below and to present research papers at a DIMACS
workshop to be held in October 1994.  A refereed workshop proceedings
will be published by the American Mathematical Society.

While massively parallel computers are routinely used in a variety of
scientific numerical applications, they are not widely used in discrete
combinatorial applications.  Within the last decade a large body of
theoretical work in parallel combinatorial algorithms has emerged.  The
impact of this theoretical work is not yet visible, and it is unclear
what kind of parallel algorithms will be most effective in practice.

The goal of this implementation challenge is to provide a forum for a
concerted experimental effort to study effective algorithms for
combinatorial problems, and to investigate the opportunities for massive
speedups on parallel computers.  The challenge is to expose, and perhaps
quantify, the issues critical to obtaining high performance on different
parallel platforms using different programming models.  For example, are
the data structures and algorithms of choice radically different for
different architectures?  What are the implications of selecting one
programming model over another (for example data-parallel versus
message-passing) to algorithm and data-structure design?  Which
algorithmic techniques are robust across machine architectures and
programming styles?

It is expected that the refereed proceedings of the workshop will
provide a state-of-the-art overview of the field, and be an invaluable
reference.  Other by-products of the challenge will be a database of
solution codes, test generators and instances, annotated bibliographies,
and other items submitted by participants.

The success of the challenge will be determined by the efforts of the
participants.  The role of DIMACS is simply to provide general guidance
and coordination, to serve as a clearing-house for exchange of programs,
benchmarks, and communication among researchers, and to sponsor the
workshop and proceedings.

\section{Description of Problem Areas}

The challenge includes two broad problem areas for research study.  The
first problem area is {\em tree searching} algorithms.  This area
includes but is not limited to branch-and-bound, backtrack, and game
tree search.  Participants can study these search problems in the
context of, say, a specific combinatorial optimization problem (e.g.
traveling salesman problem) or game-playing computer program (e.g.
chess).  Alternatively, participants may choose to develop a generic
facility for, say, branch-and-bound which can be used in different
applications.

The second problem area is parallel algorithms for sparse graphs and
dynamic graphs.  There is a large body of literature on parallel graph
algorithms as well as algorithms for updating specific properties of
dynamic graphs.  Examples include, but again are not limited to, minimum
spanning trees, shortest paths, connectivity, and graph theoretic
approaches to solving sparse linear systems.

Participants are welcome to select applications other than the examples
given above.  The aim should be to pick an application which presents
clear technical obstacles to naive parallelization, and to pick large
problem instances to warrant the use of massive parallelism.

In addition to selecting specific implementation projects, participants
should address the related issues of developing input specifications,
benchmark instances, and input generators.  Given the potential
diversity of applications as well as the variety of computing platforms,
this information will help coordinate the activities of different
researchers working on closely related applications.

\section{Computing Platforms}

Particpants are welcome to conduct their research on a computing
environment of their choice.  Included are commercially available
machines, research prototypes, workstation clusters, or even
high-performance workstations with multiple processors.  DIMACS is
currently investigating possibilities for participants to access
massively parallel processors at the NSF Supercomputing Centers across
the US.

\section{Challenge Administration} 

\subsubsection*{Advisory board}
A committee of DIMACS members will provide general direction for the
Implementation Challenge.  Committee members include Sandeep Bhatt,
Bellcore and Rutgers University (Coordinator), David Culler, U.C.
Berkeley, David Johnson, ATT-Bell Laboratories, S. Lennart Johnsson,
Thinking Machines Corporation and Harvard University, Charles
Leiserson, MIT, and Pangfeng Liu, DIMACS.

\subsubsection*{DIMACS support}
The DIMACS advisory committee will provide feedback on proposals, and
DIMACS facilities will serve as a clearing-house for exchange of
programs and communication among researchers.  DIMACS cannot provide
financial support for research projects.  

\subsubsection*{Challenge Timetable}

The Challenge continues through mid-August 1994.  During this period the
advisory committee will review short proposals from participants and
suggest alternative approaches.  Individual research groups working on
similar problems can also coordinate and exchange ideas with each other.
In order to coordinate the various events throughout the Challenge, we
suggest prospective participants follow the timetable below.

\begin{enumerate}
\item Register with the Challenge {\em as soon as possible} by sending
mail to \\challenge3@dimacs.rutgers.edu asking to be put on a mailing list
which will announce available documents and provide a forum on ongoing
research.

\item Submit a two or three page proposal by {\bf January 15, 1994}
which will be reviewed by the committee.  The proposal should briefly
describe the specific application and the experimental approach.  The
proposal should also discuss input specifications, benchmark instances,
input generators and computing platform.

Participants who select a specific application early are strongly
encouraged to send a send a brief statement (2 or 3 paragraphs) soon
after planning the project.  This will help identify projects with
similar objectives early in the challenge.

\item Submit a progress report by {\bf April 15, 1994} which will 
be reviewed by the committee.

\item Submit an (up to ten page) extended abstract by {\bf August 15, 1994}
from which workshop presenters will be chosen by the Committee.  This is
a firm deadline.

\end{enumerate}

At each review step, the committee will examine each project to identify
related, and perhaps duplicated, research efforts and to suggest
modifications as may seem appropriate and agreeable to the participants.

Approximately one month before the workshop, the set of accepted
extended abstracts in each problem domain will be circulated to those
with accepted presentations.  This will allow participants to prepare
their workshop presentations with the related papers already in mind
and will encourage further communication between participants.
Shortly after the workshop, a DIMACS technical report will be prepared
that consists of the (possibly revised) extended abstracts.  Full
papers will be due one or two months after the workshop for
consideration in the refereed proceedings.

\section{Accessing Other Documents} \label{access-doc}

A number of other documents will be ready soon.  These include an
annotated bibliography and suggested research directions.  Periodical
update on the Challenge will also be made available.  Participants are
welcome to suggest additions to the list, and to contribute to the
annotated bibliography.

Announcement of these documents will be sent to the participant
mailing list.  All these documents can be accessed by anonymous FTP,
or by sending e-mail to the Challenge.

\subsubsection*{Anonymous FTP}

The Challenge documents can be accessed via anonymous FTP to
\mbox{DIMACS}.  To use this facility type the following command
sequence.  Human-generated commands appear in {\tt typewriter} font;
{\tt name@address } refers to your full email address.

\begin{verse}
\% {\tt ftp dimacs.rutgers.edu}\\
Connected to dimacs.rutgers.edu.\\
220 dimacs.rutgers.edu FTP server (Version 6.15 Fri Apr 10 01:00:01 EDT 1992) ready.\\
Name (local.system.name): {\tt anonymous}\\
331 Guest login ok, send e-mail address as password.\\
Password: {\tt name@address}\\
230 Guest login ok, access restrictions apply.\\
ftp$>$ cd {\tt pub/challenge3}\\
250 CWD command successful.\\
\end{verse}

Typing a {\tt ?} at the {\tt ftp>} prompt will produce a list of
commands. Typing {\tt help commandname} will give a very short
description of what the command does.  Typing {\tt remotehelp
commandname} gives a description of command format.  For further
information about {\tt FTP}, contact your local system administrator. 

The main directory contains several files of general interest. The
file INDEX lists all available files and describes the various
subdirectories.

\subsubsection*{Electronic Mail}

If you do not have FTP access, the related document can also be
obtained by sending email to challenge3@dimacs.rutgers.edu and
indicating the requested files.   
 
Currently we plan to use only one address
(challenge3@dimacs.rutgers.edu) for electronic mail communication.  As
the challenge proceeds we will set up a mail-server and an Internet
newsgroup when necessary.

Please feel free to send any general questions, comments and suggestions
to \\challenge3@dimacs.rutgers.edu.

\end{document}