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