We are happy to announce the ninth iteration of PACE, the
Parameterized Algorithms and Computational Experiments Challenge. The
goals of PACE as well as official reports for past challenges can be
found on our website: https://pacechallenge.org/.
The challenge this year is an important problem in Graph Drawing:
One-Sided Crossing Minimization (OCM). This problem involves arranging the
nodes of a bipartite graph on two layers (typically horizontal), with
one of the layers fixed, aiming to minimize the number of edge crossings.
OCM is one of the basic building block used for drawing hierarchical
graphs.
It is NP-hard, even for trees, but admits good heuristics, can be
constant-factor approximated and solved in FPT time.
** Tracks
------------------------------------------------------------
This year, we will have three tracks:
**Exact:**
Your task is to find an optimal solution for each OCM
instance within 30 minutes. Here, the instances will admit a solution
with "few" crossings. You will be ranked by the number of solved
instances.
**Heuristic:**
Your task is to find the best solution for each OCM instance
within 5 minutes. You will be ranked by the quality of the solution.
**Parameterized:**
Your task is to find an optimal solution for each OCM
instance within 30 minutes. Here, the instances have small cutwidth,
but may require many crossings. A certificate for the cutwidth is
provided. You will be ranked by the number of solved instances.
** Timeline
------------------------------------------------------------
- Already present on the webpage: Tiny test instances, input and
output format descriptions, a verifier program, and more detailed
ranking information.
- November 2023: A visualizer will be provided.
- December 2023: Announcement of the ranking methods and additional
information about the submission process.
A repository for an autotester (like a JUnit test) and public test
instances will be provided
- January 2024: Public instances and details about the benchmark set get
published.
- March 2024: Submission opens with public leaderboard.
- May 2024: The public leaderboard gets frozen.
- June 2024: Submission Deadline.
- June 1st, 2024 (AoE): Submission deadline for solver.
- June 15th, 2024 (AoE): Submission deadline for solver description.
- July 2024: Announcement of the Results.
- IPEC 2024: Award ceremony.
** Zulip
------------------------------------------------------------
Join us on Zulip for discussions and updates:
https://pacechallenge.zulipchat.com/join/prysn4f3rn7grsxgmbx6vkfg/
** Program Committee
------------------------------------------------------------
- Philipp Kindermann (chair) (Universität Trier)
- Fabian Klute (UPC Barcelona)
- Soeren Terziadis (TU Eindhoven)
** Steering Committee
------------------------------------------------------------
- Max Bannach (European Space Agency)
- Sebastian Berndt (Universität zu Lübeck)
- Holger Dell (Goethe University Frankfurt and IT University of Copenhagen)
- Bart M. P. Jansen (chair) (Eindhoven University of Technology)
- Łukasz Kowalik (University of Warsaw)
- André Nichterlein (Technical University of Berlin)
- Christian Schulz (Universität Heidelberg)
- Manuel Sorge (Technische Universität Wien)