DIMACS Implementation Challenges
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
The Challenges:
The Traveling Salesman Problem
The Eighth DIMACS Implementation Challenge: 2001
WWW Site for Descriptive information.
Mailto: dsj@research.att.com for more information about participating, registering, etc.
Organized by: - David Johnson, AT&T Labs - Research
- Lyle McGeoch, Amherst College
- Fred Golver, Hearin Center for Enterprise Sciecne, University of Mississippi
- Cesar Rego, Hearin Center for Enterprise Sciecne, University of Mississippi
Semidefinite and Related Optimization Problems
The Seventh DIMACS Implementation Challenge: 2000
WWW Site for Descriptive information.
Mailto: challenge@dimacs.rutgers.edu for more information about participating, registering, etc.
Workshop Information for the November 2-3, 2000 workshop.
Organized by: - David Johnson, AT&T Labs - Research
- Gabor Pataki , Columbia University
- Farid Alizadeh, RUTCOR, Rutgers University
Near Neighbor Searches
The Sixth DIMACS Implementation Challenge: 1998
WWW Site for Descriptive information.
The Challenge Workshop on January 15, 1999.
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.
Mailto: challenge6@dimacs.rutgers.edu for more information about participating, registering, etc.
Organized by: - Michael Goldwasser, Coordinator, Princeton University
- Jon Bentley, Bell Labs
- Ken Clarkson, Bell Labs
- David Johnson, AT&T Labs
- Catherine McGeoch, Amherst College
- Robert Sedgewick, Princeton University
Priority Queues, Dictionaries, and Multi-Dimensional Point Sets
The Fifth DIMACS Implementation Challenge: 1995-1996
WWW Site for Descriptive information.
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.
Mailto: challenge@dimacs.rutgers.edu for more information about participating, registering, etc.
Workshop Information for the October 28-30, 1996 workshop.
Organized by: - Catherine McGeoch, Coordinator, Amherst College, ccm@cs.amherst.edu
- David Johnson, AT&T Bell Labs
- Richard Ladner, University of Washington
- Kurt Mehlhorn, Max Planck Institut
- Ian Munro, University of Waterloo
- Robert Sedgewick, Princeton University
- Robert Tarjan, Princeton University
Two Problems in Computational Biology:
Fragment Assembly and Genome Rearrangements
The Fourth DIMACS Implementation Challenge: 1994-1995
FTP Site
Organized by: - Martin Vingron, Coordinator, German National Research Center for Information Technology, vingron@gmd.de
- Ellson Chen, Applied Biosystems
- Sorin Istrail, Sandia National Laboratory
- David Johnson, AT&T Bell Laboratories
- John Kececioglu, University of Georgia
- Joachim Messing, Rutgers University
- Joseph Nadeau, Montreal General Hospital
- Pavel Pevzner, Pennsylvania State University
- Peter Rice, Sanger Center
- Martin Vingron, German National Research Center for Information Technology
- Michael Waterman, University of Southern California
Effective Parallel Algorithms for Combinatorial Problems
The Third DIMACS Implementation Challenge: 1993-1994
FTP Site 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.
Organized by: - Sandeep Bhatt, Coordinator, Bellcore and Rutgers, bhatt@bellcore.com
- David Culler, U.C. Berkeley
- David Johnson, AT&T Bell Laboratories
- S. Lennart Johnsson, Thinking Machines Corporation and Harvard University
- Charles Leiserson, MIT
- Pangfeng Liu, DIMACS
NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability
The Second DIMACS Implementation Challenge: 1992-1993
FTP Site 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
FTP Site 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.
Organized by: - David Johnson, Co-Coordinator, AT&T Bell Laboratories, dsj@research.att.com
- Catherine McGeoch, Co-Coordinator, Amherst College, ccm@cs.amherst.edu
- Mike Grigoriadis, Rutgers University
- Clyde Monma, Bellcore
- Bob Tarjan, Princeton University
DIMACS Home Page
Alphabetical Index of DIMACS Web Pages
Contacting the Center
Document last modified on June 11, 2003.