Abstract
This article is a report by the challenge organizers on the 9th Parameterized Algorithms and Computational Experiments Challenge (PACE 2024). As was common in previous iterations of the competition, this year’s iteration implemented an exact and heuristic track for a parameterized problem that has gained attention in the theory community. This year’s challenge is about the One-Sided Crossing Minimization Problem (OSCM). In the exact track, the competition participants were asked to develop an exact algorithm that can solve as many instances as possible from a benchmark set of 100 instances – with a time limit of 30 minutes per instance. In the heuristic track, the task must be accomplished within 5 minutes, however, the result in this track is not required to be optimal. New this year is the parameterized track, which has the same rules as the exact track, but instances are guaranteed to have small cutwidth. As in previous iterations, the organizers handed out awards to the best solutions in all tracks and to the best student submissions.
| Original language | English |
|---|---|
| Title of host publication | 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) |
| Editors | Édouard Bonnet, Paweł Rzążewski |
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Pages | 26:1-26:20 |
| Number of pages | 20 |
| ISBN (Electronic) | 978-3-95977-353-9 |
| DOIs | |
| Publication status | Published - 5 Dec 2024 |
| Event | 19th International Symposium on Parameterized and Exact Computation, IPEC 2024 - Egham, United Kingdom Duration: 4 Sept 2024 → 6 Sept 2024 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 321 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 19th International Symposium on Parameterized and Exact Computation, IPEC 2024 |
|---|---|
| Abbreviated title | IPEC 2024 |
| Country/Territory | United Kingdom |
| City | Egham |
| Period | 4/09/24 → 6/09/24 |
Funding
The prize money (\u20AC4000) was generously provided by Networks [33], an NWO Gravitation project of the University of Amsterdam, Eindhoven University of Technology, Leiden University and the Center for Mathematics and Computer Science (CWI). We are grateful to the whole optil.io team, especially to Jan Badura for the fruitful collaboration and for hosting the competition at the optil.io online judge system. We also thank Markus Wallinger, who made his exact solver available to the organizers prior to the competition for internal evaluations [38].
Keywords
- Algorithm Engineering
- FPT
- Heuristics
- One-Sided Crossing Minimization