PACE Solver Description: PACA-JAVA

Authors Jona Dirks, Mario Grobler, Roman Rabinovich, Yannik Schnaubelt, Sebastian Siebertz, Maximilian Sonneborn



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.30.pdf
  • Filesize: 449 kB
  • 4 pages

Document Identifiers

Author Details

Jona Dirks
  • University of Bremen, Germany
Mario Grobler
  • University of Bremen, Germany
Roman Rabinovich
  • Technische Universität Berlin, Germany
Yannik Schnaubelt
  • University of Bremen, Germany
Sebastian Siebertz
  • University of Bremen, Germany
Maximilian Sonneborn
  • University of Bremen, Germany

Cite AsGet BibTex

Jona Dirks, Mario Grobler, Roman Rabinovich, Yannik Schnaubelt, Sebastian Siebertz, and Maximilian Sonneborn. PACE Solver Description: PACA-JAVA. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 30:1-30:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.30

Abstract

We describe PACA-JAVA, an algorithm for solving the cluster editing problem submitted for the exact track of the Parameterized Algorithms and Computational Experiments challenge (PACE) in 2021. The algorithm solves the cluster editing problem by applying data-reduction rules, performing a layout heuristic, local search, iterative ILP verification, and branch-and-bound. We implemented the algorithm in the scope of a student project at the University of Bremen.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Cluster editing
  • parameterized complexity
  • PACE 2021

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Parameterized Algorithms and Computational Experiments. PACE 2021 - cluster editing, 2021. URL: https://pacechallenge.org/2021/cluster-editing/.
  2. Gunnar Böcker, Sebastian W.Klau and Sebastian Briesemeister. Exact algorithms for cluster editing: Evaluation and experiments. Algorithmica, 60(2):316-334, 2009. URL: https://doi.org/10.1007/s00453-009-9339-7.
  3. Thomas M. J. Fruchterman and Edward M. Reingold. Graph drawing by force-directed placement. Software: Practice and Experience, 21(11):1129-1164, 1991. URL: https://doi.org/10.1002/spe.4380211102.
  4. Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Miltenberger, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. Technical report, Optimization Online, March 2020. URL: http://www.optimization-online.org/DB_HTML/2020/03/7705.html.
  5. Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Miltenberger, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin, March 2020. URL: http://nbn-resolving.de/urn:nbn:de:0297-zib-78023.
  6. Hugh Perkins. Java wrapper for eigen c++ fast matrix library, 2016. URL: https://github.com/hughperkins/jeigen.
  7. Laurent Perron and Vincent Furnon. Or-tools. URL: https://developers.google.com/optimization/.
  8. Jonas Spinner. Weighted ℱ-free edge editing, 2019. URL: https://i11www.iti.kit.edu/_media/teaching/theses/ba-spinner-19.pdf.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail