As stated on their main 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."

The 11th Implementation Challenge is dedicated to the study of Steiner Tree problems (broadly defined), bringing together research in both theory and practice. This edition of the challenge is co-organized by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) and ICERM (Institute for Computational and Experimental Research in Mathematics). The challenge is part of the DIMACS Special Focus on Information Sharing and Dynamic Data Analysis and will be capped by a workshop hosted by ICERM at Brown University in Providence, Rhode Island, in December 2014.

Broadly speaking, the goal of a Steiner Tree problem is to find the cheapest way of connecting a set of objects. In most common variants, these objects are either points in a metric space or a subset of the vertices of a network, and the goal is to find a tree that connects all of them.

Applications of these problems abound:

• design of large-scale computer circuits;
• multicast routing in communication networks;
• network optimization;
• computer-aided design;
• phylogenetic tree reconstruction.

The main aim of the challenge is to create a reproducible picture of the state-of-the-art in Steiner Tree problems. More specifically, its goals include:

• Identify and gather (with help from all participants) a standard set of benchmark instances and generators, with emphasis on real-world applications, enabling researchers to compare codes with one another.
• Encourage the implementation and experimental evaluation of methods with theoretical performance guarantees (such as approximation algorithms), helping identify the most effective algorithmic innovations.
• Identify realistic variants of the problem taking into account constraints that appear in practice, as well as new applications of existing variants.
• Produce research papers describing the algorithms studied, the experimental results obtained, and the new instances (or generators) produced. These papers will be presented at the challenge workshop. Select papers presented at the workshop will be invited to submit to a special issue of Mathematical Programming Computation.

Participation in the challenge can take various forms, as detailed in our participation page.

The Challenge addresses the Steiner Tree problem and its variants, including:

1. classical Steiner problem in graphs;
2. classical geometric Steiner problem (including rectilinear, Euclidean, and higher dimensions);
3. prize-collecting Steiner trees;
4. dynamic Steiner trees;
5. node-weighted Steiner trees;
6. generalized Steiner trees (Steiner forest);
7. obstacle-avoiding Steiner trees;
8. directed Steiner trees (arborescences);
9. rooted Steiner trees with height (or hop) constraints;
10. group Steiner trees;
11. stochastic variants.

Submissions are not expected to address all variants, or even multiple ones, although they are welcome to do so. This list is by no means exhaustive; submissions on related variants that can use the same benchmark instances are also encouraged.