Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a greedy local search algorithm for multi-constraint hypergraph rebalancing, a critical step in achieving high-quality multi-constraint hypergraph partitioning. The algorithm provably restores balance for two constraints and bounded maximum weight by ensuring a monotonically decreasing global imbalance metric. Integrating this rebalancing step into Mt-KaHyPar yields an 11.5% geometric mean reduction in connectivity compared to Metis, demonstrating improved partition quality and balance reliability.
A surprisingly simple greedy rebalancing algorithm dramatically improves multi-constraint hypergraph partitioning, outperforming state-of-the-art methods despite limited theoretical guarantees.
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.