Networks

NETWORKS sponsor of PACE 2016

In 2016 the first edition of the Parameterized Algorithms and Computational Experiments Challenge (PACE) was launched. This challenge was supported by NETWORKS.

 

Goal

The goal of PACE is to investigate the applicability of algorithmic ideas studied and developed in the subfields of multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms. In particular, it aims to

  • provide a bridge between the theory of design and analysis of algorithms and the algorithm engineering practice,
  • inspire new theoretical developments,
  • investigate the competitiveness of analytical and design frameworks developed in the communities,
  • produce universally accessible libraries of implementations and repositories of benchmark instances, and
  • encourage the dissemination of these findings in scientific papers

 

Format of the challenge

The challenge consisted of two tracks:

 

Track A: the Tree Width Problem
Track A had a broad scope including the call for algorithms that may solve the problem heuristically and for generators of hard instances.

 

Track B: the Feedback Vertex Set Problem
Track B aimed for fixed-parameter algorithms that need to solve the Feedback Vertex Set problem exactly and had a fixed evaluation criterion.

 

For each track, participation in the challenge essentially meant submitting a program for the respective problem. The best three submissions were awarded with a prize.

 

The winners of the 1st PACE competition were presented on 24 August 2016 in Aarhus, Denmark.
There was a session dedicated to PACE as part of the 11th International Symposium

on Parameterized and Exact Computation (IPEC 2016), which was part of the larger ALGO 2016 week of co-located conferences and workshops.

 

Track A 1st prize winners

  • computing treewidth optimally with a sequential algorithm: Hisao Tamaki (Meiji University)
  • computing treewidth heuristically with a sequential algorithm: Ben Strasser (Karlsruhe Institute of Technology)
  • computing treewidth heuristically with a parallel algorithm: Kalev Kask, William Lam (University of California at Irvine)

Track B prize winners: computing optimal feedback vertex sets

  • 1st prize: Yoichi Iwata (National Institute of Informatics (NII)) and Kensuke Imanishi (University of Tokyo)
  • 2nd prize: Marcin Pilipczuk (University of Warsaw)
  • 3rd prize: Ruben Becker, Karl Bringmann, Dennis Gross, Erik Jan van Leeuwen, Natalie Wirth (MPI Saarbrücken)

The focus for PACE 2016 was the identification of specific challenge problems and an exploration of the possible organisational models to implement the main goals. It is expected that the format of PACE in the coming years will adapt to the requirements of the community, and that lessons learned from PACE 2016 will be incorporated into later studies. Researchers are encouraged to join or contact the Steering Committee to influence these developments.

 

PACE will be organized on a yearly basis.

 

More information about PACE is to be found on the website of PACE