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.34
URN: urn:nbn:de:0030-drops-154176
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15417/
Go to the corresponding LIPIcs Volume Portal

Geiger, Martin Josef

PACE Solver Description: A Simplified Threshold Accepting Approach for the Cluster Editing Problem

pdf-format:
LIPIcs-IPEC-2021-34.pdf (0.4 MB)

Abstract

We present a simple heuristic for the Cluster Editing Problem as presented in the Parameterized Algorithms and Computational Experiments (PACE) 2021. Our method makes use of a simple Threshold Accepting strategy and employs single neighborhood moves only.
Despite its simplicity, the results of the method are encouraging. However, and this has to be expected, the approach cannot ultimately win in a competitive setting such as PACE 2021. Nevertheless, some interesting insights can be derived from such a simple method, as this gives an idea of how good results can be by a comparable basic approach with a reasonable implementation effort.

BibTeX - Entry

@InProceedings{geiger:LIPIcs.IPEC.2021.34,
  author =	{Geiger, Martin Josef},
  title =	{{PACE Solver Description: A Simplified Threshold Accepting Approach for the Cluster Editing Problem}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{34:1--34:2},
  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/15417},
  URN =		{urn:nbn:de:0030-drops-154176},
  doi =		{10.4230/LIPIcs.IPEC.2021.34},
  annote =	{Keywords: Cluster Editing Problem, Threshold Accepting, Local Search}
}

Keywords: Cluster Editing Problem, Threshold Accepting, Local Search
Collection: 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Issue Date: 2021
Date of publication: 22.11.2021
Supplementary Material: Software (Source Code): https://doi.org/10.5281/zenodo.4891323

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI