KIT | KIT-Bibliothek | Impressum | Datenschutz

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


Volltext §
DOI: 10.5445/IR/1000105953
Veröffentlicht am 26.02.2020
Cover der Publikation
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 Karlsruher Institut für Technologie (KIT)
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
Externe Relationen Forschungsdaten/Software
Schlagwörter hypergraph partitioning, algorithm engineering, graph partitioning
Relationen in KITopen
Referent/Betreuer Sanders, P.
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page