The Fifth DIMACS Implementation Challenge:
Priority Queues, Dictionaries, and Point Sets
The Center for Discrete Mathematics and Theoretical Computer Science
(DIMACS) invites participation in an Implementation Challenge
to find efficient and robust implementations of
the following three data structures:
Dictionaries, Priority
Queues, and Multi-Dimensional Point Sets.
The Challenge will take place between November 1995 and
September 1996. Participants are invited to carry out research
projects related to these problem areas and to present papers
at a DIMACS workshop to be held in the fall of 1996.
Workshop proceedings will be published by the AMS. With author's
permission, the most successful implementations
will be collected for distribution by anonymous ftp.
Research Projects
The Fifth DIMACS Challenge focuses on fundamental data structures with
very wide applications. Although many theoretical papers exist
describing implementation strategies for these data structures, it
remains unclear which strategies are most efficient in practice. In the
case of multi-dimensional point sets, relatively few strategies are known
even theoretically. The goal of the DIMACS Challenge is to provide a
catalyst for experimental research in these problem areas.
Participants may wish to implement data structures for evaluation
and comparison, to build interesting problem generators, or to
develop implementations for new and parallel architectures.
Steering Committee
A Steering Committee sets policy guidelines for the Challenge.
This year's committee members are: David Johnson,
Richard Ladner,
Catherine McGeoch (Coordinator),
Kurt Mehlhorn, Ian Munro, Robert Sedgewick, and
Robert Tarjan.
DIMACS Support
The DIMACS Challenge Committee will define a standard interface for
each data structure so that implementations, problem generators, and
support tools may be exchanged by participants. Benchmark instances
will be provided for each problem as well as guidelines for research
projects. DIMACS facilities will provide a clearing-house
for communication among researchers. DIMACS can provide neither
financial support for research projects nor machine cycles for
the experiments.
How to Participate
To register for the Challenge, and/or to get on the mailing list, send an
email request to the
Challenge administrator.
The
Fifth Challenge Web Site contains more information and
resources for participants.
Support programs and documentation will also be available by
anonymous ftp from DIMACS.