Home

The goal of the Parameterized Algorithms and Computational Experiments Challenge is to investigate the applicability of algorithmic ideas studied and developed in the subfields of multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms.

PACE 2018 will be about the Steiner tree problem.

Newsletter

Be the first to learn about future PACE challenges and sign up for our low-traffic newsletter (2-4 emails per year): http://bit.ly/pace-newsletter.

PACE reports

PACE 2017

official report: http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.30

% The official bibliographic information is not available yet,
% but it should be close to the following:
@InProceedings{dell_et_al:LIPIcs:2018:PACEbestguess,
  author =	{Holger Dell and Christian Komusiewicz and Nimrod Talmon and Mathias Weller},
  title =	{{The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{30:1--30:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  year =	{2018},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  doi =		{10.4230/LIPIcs.IPEC.2017.30},
  annote =	{Keywords: treewidth, minimum fill-in, chordal completion, contest, implementation challenge, FPT}
}

Also see: Call for submissions (Track A: Treewidth, Track B: Minimum Fill-in)

PACE 2016

official report: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.30

@InProceedings{dell_et_al:LIPIcs:2017:6931,
  author =	{Holger Dell and Thore Husfeldt and Bart M. P. Jansen and Petteri Kaski and Christian Komusiewicz and Frances A. Rosamond},
  title =	{{The First Parameterized Algorithms and Computational Experiments Challenge}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{30:1--30:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6931},
  URN =		{urn:nbn:de:0030-drops-69310},
  doi =		{10.4230/LIPIcs.IPEC.2016.30},
  annote =	{Keywords: treewidth, feedback vertex set, contest, implementation challenge, FPT}
}

Also see: Call for submissions (Track A: Treewidth, Track B: Feedback Vertex Set), Results

Papers related to PACE submissions

  • Hisao Tamaki. Positive-instance driven dynamic programming for treewidth (ESA 2017, best paper award)
  • Ben Strasser. Computing Tree Decompositions with FlowCutter: PACE 2017 Submission (arXiv:1709.08949 [cs.DS])
  • Max Bannach, Sebastian Berndt and Thorsten Ehlers. Jdrasil: A Modular Library for Computing Tree Decompositions (SEA 2017)
  • Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre and Stefan Rümmele. Turbocharging Treewidth Heuristics (IPEC 2016)

Aims of PACE

We want 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
  • encourage the dissemination of these findings in scientific papers

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.

Sponsors

PACE 2016 and 2017 were supported by NWO Gravitation project ‘NETWORKS’.

Networks-logo+partners (lang)-rgb-1000px

Advertisements