# High-Quality Hypergraph Partitioning

Schlag, Sebastian

##### Abstract:
This dissertation focuses on computing high-quality solutions for the NP-hard balanced hypergraph partitioning problem: Given a hypergraph and an integer $k$, partition its vertex set into $k$ disjoint blocks of bounded size, while minimizing an objective function over the hyperedges. Here, we consider the two most commonly used objectives: the cut-net metric and the connectivity metric.

Since the problem is computationally intractable, heuristics are used in practice - the most prominent being the three-phase multi-level paradigm: During coarsening, the hypergraph is successively contracted to obtain a hierarchy of smaller instances. ... mehr

##### Abstract (englisch):
This dissertation focuses on computing high-quality solutions for the NP-hard balanced hypergraph partitioning problem: Given a hypergraph and an integer $k$, partition its vertex set into $k$ disjoint blocks of bounded size, while minimizing an objective function over the hyperedges. Here, we consider the two most commonly used objectives: the cut-net metric and the connectivity metric.

Since the problem is computationally intractable, heuristics are used in practice -- the most prominent being the three-phase multi-level paradigm: During coarsening, the hypergraph is successively contracted to obtain a hierarchy of smaller instances. ... mehr

 Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI) Publikationstyp Hochschulschrift Publikationsdatum 26.02.2020 Sprache Englisch Identifikator KITopen-ID: 1000105953 HGF-Programm 46.12.02 (POF III, LK 01)Data Activities Verlag Karlsruhe Umfang XI, 283 S. Art der Arbeit Dissertation Fakultät Fakultät für Informatik (INFORMATIK) Institut Institut für Theoretische Informatik (ITI) Prüfungsdatum 11.12.2019 Referent/Betreuer Prof. P. Sanders Externe Relationen Forschungsdaten/Software Schlagwörter hypergraph partitioning, algorithm engineering, graph partitioning Relationen in KITopen Verweist aufBenchmark Sets used in the Dissertation of Sebastian Schlag. Schlag, Sebastian (2019) Forschungsdaten (1000098881)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page