License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.26
URN: urn:nbn:de:0030-drops-154096
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15409/
Kellerhals, Leon ;
Koana, Tomohiro ;
Nichterlein, André ;
Zschoche, Philipp
The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing
Abstract
The Parameterized Algorithms and Computational Experiments challenge (PACE) 2021 was devoted to engineer algorithms solving the NP-hard Cluster Editing problem, also known as Correlation Clustering: Given an undirected graph the task is to compute a minimum number of edges to insert or remove in a way that the resulting graph is a cluster graph, that is, a graph in which each connected component is a clique.
Altogether 67 participants from 21 teams, 11 countries, and 3 continents submitted their implementations to the competition. In this report, we describe the setup of the challenge, the selection of benchmark instances, and the ranking of the participating teams. We also briefly discuss the approaches used in the submitted solvers.
BibTeX - Entry
@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2021.26,
author = {Kellerhals, Leon and Koana, Tomohiro and Nichterlein, Andr\'{e} and Zschoche, Philipp},
title = {{The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {26:1--26:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-216-7},
ISSN = {1868-8969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15409},
URN = {urn:nbn:de:0030-drops-154096},
doi = {10.4230/LIPIcs.IPEC.2021.26},
annote = {Keywords: Correlation Clustering, Cluster Editing, Algorithm Engineering, FPT, Kernelization, Heuristics}
}
