This website has been archived and is no longer actively maintained
To learn about more recent Implementation Challenges, go to the
new Implementation Challenge website.
The DIMACS Implementation Challenges
address questions of determining realistic algorithm performance
where worst case analysis is overly
pessimistic and probabilistic models are too unrealistic:
experimentation can provide guides to realistic algorithm performance
where analysis fails.
Experimentation also brings algorithmic questions closer to the
original problems that motivated theoretical work.
It also tests many assumptions about implementation methods and data
structures. It provides an opportunity to develop and test
problem instances, instance generators, and other methods of testing
and comparing performance of algorithms. And it is a step in technology transfer
by providing leading edge implementations of algorithms for others to adapt.
The information on challenges includes pointers to WWW/FTP sites that
include calls for participation, algorithm implementations, instance generators,
bibliographies, and other electronic artifacts.
The challenge organizers are also producing refereed volumes in the
AMS-DIMACS book series; these contain selected papers from the workshops
that culminate each challenge.
If you are using the implementations, generators or other files,
please take a few minutes to tell us how you are using it, what applications
you are working on, and how it impacts your work.
We need to document the impact of this research to the agencies and
foundations that support it - your stories are essential to doing that.
Send comments to:
froberts@dimacs.rutgers.edu
The Famous DIMACS Graph Format
Quite a few research papers have been referring to the DIMACS
graph format.
The first Challenge used networks (directed graphs with edge and
node capacities) and undirected graphs (for matching), and the second
Challenge used undirected graph. Extending these formats to directed
graphs should be straightforward. Specifications for the Challenge 1
formats are available by anonymous ftp (or through the DIMACS web page
Previous Challenges) in
Selected Papers: of the challenge; see Volume 59, "Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges", Editors: Michael H. Goldwasser, David S. Johnson and Catherine C. McGeoch; AMS, Providence, RI, 2002.
Selected Papers: of the challenge; see Volume 59, "Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges", Editors: Michael H. Goldwasser, David S. Johnson and Catherine C. McGeoch; AMS, Providence, RI, 2002.
Selected Papers:
of the challenge; see Volume 30, Parallel Algorithms: Third DIMACS Implementation Challenge, October 17-19, 1994,
Editors: Sandeep N. Bhatt; AMS, Providence, RI, 1997.
Selected Papers:
of the challenge; see Volume 26, Cliques, Coloring, and Satisfiability:
Second DIMACS Implementation Challenge, October 11-13, 1993,
Editors: David S. Johnson and Michael A. Trick;
AMS, Providence, RI, 1996.
Organized by:
Michael Trick, Coordinator, DIMACS Visiting Fellow & Carnegie Mellon University
trick@mat.gsia.cmu.edu
Vavsek Chvatal, Rutgers University
Bill Cook, Bell Communications Research
David Johnson, AT&T Bell Laboratories
Cathy McGeoch, Amherst College
Bob Tarjan, Princeton University
Network Flows and Matching
The First DIMACS Implementation Challenge: 1990-1991
Selected Papers:
of the challenge; see Volume 12, Network Flows and Matching:
First DIMACS Implementation Challenge, Editors: David S. Johnson and Catherine C. McGeoch;
AMS, Providence, RI, 1993.
DIMACS Home Page