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.SEA.2023.17
URN: urn:nbn:de:0030-drops-183674
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18367/
Wahl, Noah ;
Gottesbüren, Lars
Greedy Heuristics for Judicious Hypergraph Partitioning
Abstract
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.
BibTeX - Entry
@InProceedings{wahl_et_al:LIPIcs.SEA.2023.17,
author = {Wahl, Noah and Gottesb\"{u}ren, Lars},
title = {{Greedy Heuristics for Judicious Hypergraph Partitioning}},
booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)},
pages = {17:1--17:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-279-2},
ISSN = {1868-8969},
year = {2023},
volume = {265},
editor = {Georgiadis, Loukas},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18367},
URN = {urn:nbn:de:0030-drops-183674},
doi = {10.4230/LIPIcs.SEA.2023.17},
annote = {Keywords: hypergraph partitioning, local search algorithms, load balancing, local search}
}
