KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel and Flow-Based High Quality Hypergraph Partitioning

Gottesbüren, Lars 1
1 Fakultät für Informatik (INFORMATIK), Karlsruher Institut für Technologie (KIT)

Abstract (englisch):

Balanced hypergraph partitioning is a classic NP-hard optimization problem that is a fundamental tool in such diverse disciplines as VLSI circuit design, route planning, sharding distributed databases, optimizing communication volume in parallel computing, and accelerating the simulation of quantum circuits.
Given a hypergraph and an integer $k$, the task is to divide the vertices into $k$ disjoint blocks with bounded size, while minimizing an objective function on the hyperedges that span multiple blocks.
In this dissertation we consider the most commonly used objective, the connectivity metric, where we aim to minimize the number of different blocks connected by each hyperedge.

The most successful heuristic for balanced partitioning is the multilevel approach, which consists of three phases.
In the coarsening phase, vertex clusters are contracted to obtain a sequence of structurally similar but successively smaller hypergraphs.
Once sufficiently small, an initial partition is computed.
Lastly, the contractions are successively undone in reverse order, and an iterative improvement algorithm is employed to refine the projected partition on each level.
... mehr


Volltext §
DOI: 10.5445/IR/1000157894
Veröffentlicht am 19.04.2023
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Informatik (INFORMATIK)
Publikationstyp Hochschulschrift
Publikationsdatum 19.04.2023
Sprache Englisch
Identifikator KITopen-ID: 1000157894
Verlag Karlsruher Institut für Technologie (KIT)
Umfang ix, 240 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 17.11.2022
Schlagwörter hypergraph partitioning, parallel algorithms, shared-memory parallelism, algorithm engineering, multilevel algorithms
Referent/Betreuer Wagner, Dorothea
Meyerhenke, Henning
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page