2026-07-25T05:29:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22259 2024-12-05T15:32:41Z ddc:004 open_access

PACE Solver Description: Arcee Boehmer, Kimon George, Lukas Lee Hauser, Fanny Palarus, Jesse PACE 2024 One-Sided Crossing Minimization OCM The 2024 PACE Challenge focused on the One-Sided Crossing Minimization (OCM) problem, which aims to minimize edge crossings in a bipartite graph with a fixed order in one partition and a free order in the other. We describe our OCM solver submission that utilizes various reduction rules for OCM and, for the heuristic track, employs local search approaches as well as techniques to escape local minima. The exact solver uses an ILP formulation and branch & bound to solve an equivalent Feedback Arc Set instance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kimon Boehmer and Lukas Lee George and Fanny Hauser and Jesse Palarus 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.33 urn:nbn:de:0030-drops-222595 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.33 eng https://creativecommons.org/licenses/by/4.0/legalcode