Given an undirected edge-weighted graph G and a subset T (terminals) of its vertices, find a subgraph of G spanning T with the smallest total edge-weight.
TRACK 1 (Exact with few terminals)
You have 30 minutes per instance.
Win by solving more instances than the other participants.
In all the instances, there are only a few terminals.
TRACK 2 (Exact with low treewidth)
You have 30 minutes per instance.
Win by solving more instances than the other participants.
In this track only, the instances come with a tree decomposition and the treewidth is low.
TRACK 3 (Heuristic)
Here the instances are significantly larger, have many terminals, and high treewidth, but you are not expected to find an optimum solution.
You still have 30 minutes per instance.
Win by finding Steiner trees of smaller weight than the other participants.
We will rank by average approximation ratio.
Detailed instructions about the three tracks, their rules, the instance sets, and the input and output formats: https://pacechallenge.wordpress.com/pace-2018/
You can already register for the challenge: https://docs.google.com/forms/d/e/1FAIpQLScHH6lNpUYwLT6GDVMO9ik0s9iwhQTRbxnaJED1wdZOWBtJRg/viewform .
You can also download the public instances on the PACE challenge website and start your implementation.
As for the previous edition, we cooperate with the platform optil.io (https://www.optil.io/optilion/).
In a short while, you will be able to run your code on this platform.
We will let you know when it is ready and how to proceed.
TIMELINE:
November 14th, 2017: Announcement of the challenge
May 1st, 2018: Submission of final program
May 10th, 2018: Result are communicated to participants
August 20-24 2018: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2018) in Helsinki
PROGRAM COMMITTEE:
Track 1, 2, 3:
- Édouard Bonnet (Middlesex University, London)
- Florian Sikora (Paris-Dauphine University)
STEERING COMMITTEE:
- Holger Dell (Saarland University and Cluster of Excellence, MMCI)
- Bart M. P. Jansen (chair) (Eindhoven University of Technology)
- Thore Husfeldt (ITU Copenhagen and Lund University)
- Petteri Kaski (Aalto University)
- Christian Komusiewicz (Friedrich-Schiller-University Jena)
- Frances A. Rosamond (University of Bergen)
Best of luck with your code!
The PACE Committees
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
