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.