Search Results

Documents authored by Wienöbst, Marcel

Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2024.28
PACE Solver Description: UzL Exact Solver for One-Sided Crossing Minimization

Authors: Max Bannach, Florian Chudigiewitsch, Kim-Manuel Klein, and Marcel Wienöbst

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
This document contains a short description of our solver pingpong for the one-sided crossing minimization problem that we submitted to the exact and parameterized track of the PACE challenge 2024. The solver is based on the well-known reduction to the weighted directed feedback arc set problem. This problem is tackled by an implicit hitting set formulation using an integer linear programming solver. Adding hitting set constraints is done iteratively by computing heuristic solutions to the current formulation and finding cycles that are not yet "hit." The procedure terminates if the exact hitting set solution covers all cycles. Thus, optimality of our solver is guaranteed.
Cite as

Max Bannach, Florian Chudigiewitsch, Kim-Manuel Klein, and Marcel Wienöbst. PACE Solver Description: UzL Exact Solver for One-Sided Crossing Minimization. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 28:1-28:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.IPEC.2024.28,
  author =	{Bannach, Max and Chudigiewitsch, Florian and Klein, Kim-Manuel and Wien\"{o}bst, Marcel},
  title =	{{PACE Solver Description: UzL Exact Solver for One-Sided Crossing Minimization}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{28:1--28:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.28},
  URN =		{urn:nbn:de:0030-drops-222548},
  doi =		{10.4230/LIPIcs.IPEC.2024.28},
  annote =	{Keywords: integer programming, exact algorithms, feedback arc set, crossing minimization}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2020.27
PACE Solver Description: Fluid

Authors: Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
This document describes the heuristic for computing treedepth decompositions of undirected graphs used by our solve fluid. The heuristic runs four different strategies to find a solution and finally outputs the best solution obtained by any of them. Two strategies are score-based and iteratively remove the vertex with the best score. The other two strategies iteratively search for vertex separators and remove them. We also present implementation strategies and data structures that significantly improve the run time complexity and might be interesting on their own.
Cite as

Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst. PACE Solver Description: Fluid. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 27:1-27:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.IPEC.2020.27,
  author =	{Bannach, Max and Berndt, Sebastian and Schuster, Martin and Wien\"{o}bst, Marcel},
  title =	{{PACE Solver Description: Fluid}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{27:1--27:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.27},
  URN =		{urn:nbn:de:0030-drops-133300},
  doi =		{10.4230/LIPIcs.IPEC.2020.27},
  annote =	{Keywords: treedepth, heuristics}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2020.28
PACE Solver Description: PID^⋆

Authors: Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
This document provides a short overview of our treedepth solver PID^{⋆} in the version that we submitted to the exact track of the PACE challenge 2020. The solver relies on the positive-instance driven dynamic programming (PID) paradigm that was discovered in the light of earlier iterations of the PACE in the context of treewidth. It was recently shown that PID can be used to solve a general class of vertex pursuit-evasion games - which include the game theoretic characterization of treedepth. Our solver PID^{⋆} is build on top of this characterization.
Cite as

Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst. PACE Solver Description: PID^⋆. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 28:1-28:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.IPEC.2020.28,
  author =	{Bannach, Max and Berndt, Sebastian and Schuster, Martin and Wien\"{o}bst, Marcel},
  title =	{{PACE Solver Description: PID^⋆}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{28:1--28:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.28},
  URN =		{urn:nbn:de:0030-drops-133312},
  doi =		{10.4230/LIPIcs.IPEC.2020.28},
  annote =	{Keywords: treedepth, positive-instance driven}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact