2026-07-22T21:01:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18367 2024-03-06T11:01:37Z ddc:004 open_access

Greedy Heuristics for Judicious Hypergraph Partitioning Wahl, Noah Gottesbüren, Lars hypergraph partitioning local search algorithms load balancing local search We investigate the efficacy of greedy heuristics for the judicious hypergraph partitioning problem. In contrast to balanced partitioning problems, the goal of judicious hypergraph partitioning is to minimize the maximum load over all blocks of the partition. We devise strategies for initial partitioning and FM-style post-processing. In combination with a multilevel scheme, they beat the previous state-of-the-art solver - based on greedy set covers - in both running time (two to four orders of magnitude) and solution quality (18% to 45%). A major challenge that makes local greedy approaches difficult to use for this problem is the high frequency of zero-gain moves, for which we present and evaluate counteracting mechanisms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noah Wahl and Lars Gottesbüren 2023 Is Part Of LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2023.17 urn:nbn:de:0030-drops-183674 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.17 eng https://creativecommons.org/licenses/by/4.0/legalcode