2026-08-25T17:34:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27148 2026-08-25T13:18:15Z ddc:004 open_access

High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing Maas, Nikolai Hypergraph Partitioning Multi-Constraint Partitioning Graph Algorithms Multilevel Algorithms Local Search Vector Scheduling Multidimensional Load Balancing Multi-constraint hypergraph partitioning is a generalization of balanced partitioning, where the vertex set of a hypergraph is partitioned such that the inter-block connectivity of hyperedges is minimized while balancing the vertices with regard to d distinct constraints. A prominent class of applications is data distribution tasks, where this allows to achieve good load balance for d different kinds of resources and simultaneously minimize the communication volume. Although the best approaches for single-constraint partitioning are usually complex (multilevel) algorithms with many components, we show that replacing only one component already leads to high-quality multi-constraint partitions: the rebalancing step, which restores balance for a partition that has (hopefully) small connectivity but violates the constraints. We design a multi-constraint rebalancing algorithm based on greedy local search, proving that balance is always restored for d = 2 and bounded maximum weight. The key is to ensure monotonically decreasing global imbalance by choosing an imbalance metric where there is always a balance-improving move available. Integrating our algorithm into the state-of-the-art partitioner Mt-KaHyPar, we demonstrate an 11.5 % geometric mean connectivity reduction compared to the next best competitor (Metis) and better reliability regarding partition balance, even though the majority of inputs is outside of the theoretical guarantee. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikolai Maas 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.12 urn:nbn:de:0030-drops-271480 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.12 eng https://creativecommons.org/licenses/by/4.0/legalcode