PACE 2018 is generously sponsored by NETWORKS, an NWO Gravitation project of the University of Amsterdam, Eindhoven University of Technology, Leiden University, and the Center for Mathematics and Computer Science (CWI); see http://thenetworkcenter.nl/ . Through their support, we can hereby announce a total of 4000 euros of sponsoring that will be divided into prizes and travel awards for participants.
The challenge this year consists of three tracks on the Steiner Tree problem:
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 register for the challenge here: 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/).
You can test your code on this platform now: https://pacechallenge.wordpress.com/2017/12/12/optil-io/ .
TIMELINE:
November 14th, 2017: Announcement of the challenge
December 12th, 2017: PACE 2018 test inputs on optil.io
February 2nd, 2018: Announcement of NETWORKS sponsoring and prizes
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
