\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}

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

\section{Introduction}

Participation is invited for an international Implementation Challenge 
to find and evaluate efficient and robust implementations of algorithms for 
the {\em minimum-cost flow} problem,
the {\em maximum flow} problem, the {\em assignment} problem, 
and {\em nonbipartite matching}. 
The project is sponsored by 
the Center for Discrete Mathematics and Theoretical 
Computer Science (DIMACS) with support from the National Science 
Foundation.
%\footnote{This material is based upon work supported by 
%the National Science Foundation under RUI Grant No. CCR-9013079.  The 
%Government has certain rights in this material.  Any opinions, findings,
%and conclusions or recommendations expressed in this material are those of 
%the author and do not necessarily reflect the views of the National 
%Science Foundation.} 

The Implementation Challenge will take place between November 1990 and
August 1991. Challenge participants are invited
to submit research papers for presentation at a DIMACS workshop to 
be held in Fall 1991;  some travel support will be available.  
Workshop proceedings will be published. 
Best Paper awards, in the form of certificates of recognition, will 
be presented in several categories;  with author's permission, the 
most successful implementations will be collected for distribution 
on floppy disk.  

There are several ways to participate in the Challenge, 
as described below. 

\paragraph{1. Implement and evaluate algorithms.}

Participants may implement 
one or more algorithms (or perhaps alternative data structures or 
strategies for a single algorithm) for experimental evaluation. 
Several new algorithms for flow and matching problems have recently
appeared in theoretical papers.  How does their performance in practice
relate to their theoretical analyses?  How well do they stack up against
older approaches?   

DIMACS will provide a set of benchmark inputs for each problem; 
participants are invited to perform more  
extensive tests as desired. 
Guidelines and support tools for experimental study are 
also available from DIMACS.  

\paragraph{2. Create test inputs and input generators.}

Participants are also invited to submit test inputs or input generators for 
these problems. 
\begin{itemize}
\item For the network problems 
we invite generators of ``random'' inputs having some quantifiable 
combinatorial structure and which suggest a useful model 
of average-case performance. 
Those with features that complement or extend the 
widely available NETGEN \cite{kns} generator are especially invited. 

\item For the matching problem, we invite input generators 
which present instances suitable for testing correctness as well 
as efficiency. 

\item Also of interest are generators of inputs that are arguably ``hard'' 
for certain algorithms (causing loss of efficiency), and which can be 
used to distinguish algorithmic robustness with respect to input. 

\item Input instances from real applications are welcome. 
\end{itemize} 

Authors of test generators should be able to describe the kinds of 
instances generated and to argue why they are interesting.  They 
should perform at least limited tests to determine whether their generators
yield different answers than the standard benchmarks.  
With author's permission, submitted inputs and generators 
will be made available to Challenge participants;  some may be 
included in the set of DIMACS benchmarks.  

Generated inputs are expected to follow a
standard format; see Section 4 for further information. 

\paragraph{3. Test on an unusual architecture or environment.}

Participants with access to a machine not widely available 
are invited to adapt algorithms (or existing programs) 
for testing on that architecture.  Implementations tuned for a particular
architecture (Cray, Connection Machine, etc.) are welcome; we are also
interested in collecting benchmark statistics for such machines 
on a standard set of codes and inputs available from DIMACS.  

\section{Challenge Goals, Rules, and Specifications} 

A committee of members affiliated with DIMACS will 
set policy, develop guidelines, and provide general direction
for the Implementation
Challenge.  Committee members are Mike Grigoriadis (Rutgers University), 
David Johnson (AT\&T Bell 
Laboratories), Cathy  McGeoch  (Chairperson, 
DIMACS Visiting Fellow/Amherst College), 
Clyde Monma (Bell Communications Research), and Bob Tarjan 
(Princeton University). 

DIMACS can provide neither financial support for research projects nor
machine cycles for the experiments, although some limited confirmatory 
tests will be carried out at DIMACS.   
The intent of the Challenge is to use DIMACS facilities (and the Internet), 
to provide a catalyst for experimental research on flow and matching 
problems, to promote communication among researchers in these areas, and to 
provide a clearing-house for exchange of implementations and
input generators.   A successful Challenge (measured by the level of 
participation and quality of research generated) will pave the way for 
future yearly projects in other areas of discrete
mathematics and theoretical computer science.  

One goal of the project is to test the suitability of the Internet
for cooperative research of this type.  
{\em All communication regarding the Implementation Challenge will take place
via Internet.}  See Section 4 for further information. 

\paragraph{Project proposals.} 

We request that each participant register (to be put on the mailing list), 
and submit a one-page proposal for a research project. 
No proposal will be  rejected:  the committee will review each 
to identify duplicated research efforts and to suggest 
modifications as may seem appropriate.  

Section 3 briefly surveys the problem areas and lists some open problems. 
A file containing suggested projects is available via 
anonymous FTP; see Section 4 for further information. 

\paragraph{Levels of Participation.}

Three levels of participation will be recognized. Certain award 
categories will be limited to the first and second levels of 
participation only. 

\begin{itemize}
\item {\em Public domain code.}  Participants at this level 
agree to make implementations available for limited verification and testing 
at DIMACS and to permit public distribution of their code.
Creators of such code should document their authorship with 
comments and should expect appropriate citation from users
of the code. 

\item {\em DIMACS-compilable code.} Participants may submit code for
limited validation and comparative testing at DIMACS but {\em not} for 
public distribution.  
Send mail to {\bf netflow@dimacs.rutgers.edu} for a policy statement
regarding DIMACS use of such codes. 

Participants at these two levels should
produce implementations which can be run on the Sun SPARC 1 workstations
supported at DIMACS.  The operating system is UNIX SunOS 4.0.3c.  
Suggested languages are C, Pascal and Fortran (compatible with FORTRAN 77
and VMS Fortran). 

Participants with compatible implementations will be able to make full
use of the support tools provided by DIMACS.  In general we do not 
expect to perform extensive tests at DIMACS, nor will we verify 
program correctness.  Some computational testing may be undertaken 
to assess the effect of different programming environments or 
to confirm unusual test results.  

\item {\em Private domain code.} Challenge participants may wish to develop 
code which is to be kept private or which cannot be run on DIMACS
machines. Such participants may present research papers at the
workshop.
\end{itemize}

\paragraph{Important Dates.}

\begin{itemize}
\item The Challenge begins November 1990 and continues through 
August 1991. Send mail to {\bf netflow@dimacs.rutgers.edu} to be put
on the mailing list or to submit a project proposal.

Support code, program development and testing tools, input generators,
and input instances may be submitted and are welcome at any time.  See
Section 4 for submission information.  General announcements of new
files and test inputs available from DIMACS will be made periodically.

\item Project proposals will be accepted any time through 
{\bf January 31, 1991}.

\item Initial progress reports are due on {\bf March 1, 1991}.  Participants   
should provide a two-or-three page summary of test results for the
DIMACS benchmarks or of preliminary results as appropriate to the
project.  Contributors of input generators are requested to submit
(perhaps preliminary) implementations by this time to allow timely
redistribution and use.  The DIMACS committee will provide comments
and suggestions for improving or extending the experiments and for 
the presentation of results. 

\item  The Challenge ends {\bf August 1, 1991}, in 
the sense that all tests using the official input set must be
completed, and a 10 page abstract summarizing the research results 
must be submitted.  Participants may of course 
continue with related or more extensive testing as desired.

\item A workshop will be held in {\bf Fall 1991};  papers presented
at the workshop must be submitted at that time for inclusion in the
subsequently published workshop proceedings.  Successful 
implementations will be collected for distribution on a floppy disk.
\end{itemize}

\paragraph{Problem Definitions and Input/Output Specifications.} 

To achieve compatibility of input generators and test implementations,
a standard  input format has been defined for each problem. 
Translation programs for converting to and from other standard network 
representations  will be distributed as they become available. 

A companion document is available from DIMACS 
containing problem definitions and specifications of input and output formats. 
Send a note requesting {\em Problem Definitions and Specifications}
to {\bf netflow@dimacs.rutgers.edu}. 
Request either a \LaTeX$\;$ file (sent through email) or a hard copy
(sent through U.S. Mail), and include return address as appropriate.  

\section{Suggested Research Projects} 

For a more complete discussion of the problems included in the
Implementation Challenge, see {\em Problem Definitions and 
Specifications}, mentioned in the previous section.  

Problems relating to network flows were described by Ford and Fulkerson
\cite{forful}, who obtained  several classic results.  Many introductory
texts are available concerning network flow problems:  see for 
example Derigs \cite{derigs}, 
Jensen and Barnes \cite{jenbar}, Lawler \cite{lawler},
Papadimitriou and Steiglitz \cite{papste},  
Rockafellar \cite{rockafellar}, or  Tarjan \cite{tarjan}. 
Surveys of recent work in flow problems are found in 
Ahuja et al. \cite{amo} and Goldberg et al.\cite{gtt}. 
Texts by Papadimitriou and Steiglitz \cite{papste} and 
Tarjan \cite{tarjan} describe the matching problem and give 
references to related work. 

Several recent papers on these topics may 
be found in STOC, FOCS, and SODA proceedings, and in journals such as 
{\em Journal of Algorithms}, {\em Journal of the ACM},
{\em Management Science}, 
{\em Mathematical Programming}, 
{\em Operations Research}, and {\em SIAM Journal on Computing}. 

Some research projects suitable for the Implementation Challenge are
listed below.  See Section 4 for information on obtaining more open problems. 

\begin{enumerate}
\item Implement an algorithm with interesting theoretical properties
that has not been  previously implemented.  While running times are
useful, experiments which report performance
in terms of combinatorial measures (by counting significant operations)
are of particular interest.  

\item Linear programming can be applied to any of the network flow problems. 
Compare the interior point method for linear programming to 
network simplex approaches (and to combinatorial algorithms).

\item Although scaling techniques are useful in improving
theoretical bounds, it is not clear whether scaling is helpful
in speeding up implementations of these algorithms.  Evaluate their 
sensitivity to input properties.  

\item It appears difficult to develop an implementation for the
matching problem which is clearly correct for all inputs.  Design an 
input generator that ``stresses'' matching programs by presenting, 
say, inputs that cause the appearance of blossoms with multiple nesting 
(see \cite{edmonds} or \cite{tarjan}).  

\item Goldberg, Tardos, and Tarjan \cite{gtt} (Sections 2.2-2.4) describe a 
generic push-relabel algorithm for the maximum flow problem.  
Two implementation issues arize:  the order of selection of 
active vertices,  and the choice of data structure for maintaining
arc information. Discover which choices are best for 
various input classes.   

\item  Many well-known combinatorial optimization problems are 
specializations of minimum-cost flow or maximum flow.  Design instance
generators based upon applications and evaluate the general algorithms
for these inputs. 

\item Compare specialized algorithms to general algorithms for 
certain problems.  For example, there a maximum flow algorithm specialized
for bipartite instances which is more efficient than general 
algorithms running on bipartite instances?   

\item  Vaidya \cite{vaidya} suggests algorithms for 
assignment and matching which are theoretically 
more efficient on geometric networks and graphs than algorithms
for general costs.  Compare the algorithm in \cite{vaidya} to one or 
more other algorithms on geometric graphs for several distance metrics. 

\end{enumerate} 

\section{How to Find Out More}

\subsection{Anonymous FTP}
Several programs and data files are available via anonymous FTP to 
DIMACS.   To use this facility type the following command sequence. 
Human-generated commands appear in {\tt typewriter
font}; {\tt loginid } refers to your local login id. 
\begin{verse}
\$ {\tt ftp dimacs.rutgers.edu}  \\
Connected to dimacs.rutgers.edu. \\
220 dimacs.rutgers.edu FTP server (SunOS 4.0) ready. \\
Name (dimacs.rutgers.edu:loginid): {\tt anonymous}\\
331 Guest login ok, send ident as password. \\
Password: {\tt loginid} \\
230 Guest login ok, access restrictions apply. \\
ftp{\tt >cd pub/netflow}
\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.  Some useful commands are listed below. 
\begin{description}

\item[cd directoryname]  Change to the named subdirectory. 

\item[cdup] Change to the parent of the current directory. 

\item[dir] Give a verbose listing of directory contents. Command {\bf ls}
lists file and subdirectory names only.  

\item[get] Copy a file from remote site to local directory; the system 
prompts for remote and local filenames.  

\item[put] Insert a file into remote directory; prompts for local andvremote filenames.  

\item[quit] Terminate the FTP connection. 
\end{description}

The main directory contains several files of general interest. 
Four subdirectories contain files relating to each of the four problems;
they are named {\bf mincost}, {\bf maxflow}, {\bf assignment}, and 
{\bf matching}.  Other subdirectories and files include the following. 

\begin{description}

\item[INDEX] Lists available files and their sizes.

\item[README]  Contains general instructions or information on using the 
subdirectory contents. 

\item[open\_problems] Contains descriptions of suggested research 
projects.  

\item[general]  A subdirectory containing general information and
guidelines for the Challenge.  

\item[benchmarks] This subdirectory contains  benchmark programs, 
input files, and shell scripts for running benchmark tests for 
each problem.  We request that each  participant run these 
benchmarks in the local environment so that we may calibrate results. 

\item[official\_inputs] This subdirectory contains the 
official set of DIMACS test inputs and generators for each problem.  

\item[other\_inputs] This subdirectory contains other instances and
generators of interest.  

\item[submit]  This publically-writable directory contains
submitted programs and data files.  Submittors should examine 
directory contents to avoid overwriting files with identical names. 
\end{description} 

\subsection{Electronic Mail}

Some participants may not have capabilities for anonymous FTP.  In this
case files and related information can be obtained by electronic mail.
The following addresses may be used.  
\begin{description}
\item[netflow@dimacs.rutgers.edu] Requests to be put on the mailing list,
project proposals, general questions and comments should be sent to this 
address. 

\item[netflow-submit@dimacs.rutgers.edu] Submitted programs and data files may
be mailed to this address.  If a submission consists of more than one file,
please bundle all files into a single mail message, preferably using the
commonly available ``shar'' utility.

\item[netlib@dimacs.rutgers.edu] This is an automatic mail server, from which
files can be requested.  For help using it, send a message to it with the
subject ``help''.

% this really doesn't apply anymore? -dpz
% \item (Other addresses for automatic replies may be implemented. ) 

\end{description} 

\bibliographystyle{plain}
\bibliography{flow}
\end{document}

