KIT | KIT-Bibliothek | Impressum | Datenschutz

Multilevel Hypergraph Partitioning with Vertex Weights Revisited

Heuer, Tobias ORCID iD icon; Maas, Nikolai; Schlag, Sebastian


The balanced hypergraph partitioning problem (HGP) is to partition the vertex set of a hypergraph into k disjoint blocks of bounded weight, while minimizing an objective function defined on the hyperedges. Whereas real-world applications often use vertex and edge weights to accurately model the underlying problem, the HGP research community commonly works with unweighted instances. In this paper, we argue that, in the presence of vertex weights, current balance constraint definitions either yield infeasible partitioning problems or allow unnecessarily large imbalances and propose a new definition that overcomes these problems. We show that state-of-the-art hypergraph partitioners often struggle considerably with weighted instances and tight balance constraints (even with our new balance definition). Thus, we present a recursive-bipartitioning technique that is able to reliably compute balanced (and hence feasible) solutions. The proposed method balances the partition by pre-assigning a small subset of the heaviest vertices to the two blocks of each bipartition (using an algorithm originally developed for the job scheduling problem) and optimizes the actual partitioning objective on the remaining vertices. ... mehr

Verlagsausgabe §
DOI: 10.5445/IR/1000134591
Veröffentlicht am 01.07.2021
DOI: 10.4230/LIPIcs.SEA.2021.8
Zitationen: 3
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsdatum 31.05.2021
Sprache Englisch
Identifikator ISBN: 978-3-95977-185-6
ISSN: 1868-8969
KITopen-ID: 1000134591
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Erschienen in 19th International Symposium on Experimental Algorithms (SEA 2021)
Veranstaltung 19th International Symposium on Experimental Algorithms (SEA 2021), Nizza, Frankreich, 07.06.2021 – 09.06.2021
Auflage 190
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten 8:1-8:20
Serie Leibniz International Proceedings in Informatics (LIPIcs Ed.: D. Coudert ; 190
Schlagwörter multilevel hypergraph partitioning, balanced partitioning, vertex weights
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page