KIT | KIT-Bibliothek | Impressum | Datenschutz

Scalable High-Quality Graph and Hypergraph Partitioning

Heuer, Tobias ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

The balanced hypergraph partitioning problem (HGP) asks for a partition of the node set
of a hypergraph into $k$ blocks of roughly equal size, such that an objective function defined
on the hyperedges is minimized. In this work, we optimize the connectivity metric,
which is the most prominent objective function for HGP.

The hypergraph partitioning problem is NP-hard and there exists no constant factor approximation.
Thus, heuristic algorithms are used in practice with the multilevel scheme as
the most successful approach to solve the problem: First, the input hypergraph is coarsened to
obtain a hierarchy of successively smaller and structurally similar approximations.
The smallest hypergraph is then initially partitioned into $k$ blocks, and subsequently,
the contractions are reverted level-by-level, and, on each level, local search algorithms are used
to improve the partition (refinement phase).

In recent years, several new techniques were developed for sequential multilevel partitioning
that substantially improved solution quality at the cost of an increased running time.
These developments divide the landscape of existing partitioning algorithms into systems that either aim for
... mehr


Volltext §
DOI: 10.5445/IR/1000152872
Veröffentlicht am 24.11.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsdatum 24.11.2022
Sprache Englisch
Identifikator KITopen-ID: 1000152872
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Verlag Karlsruher Institut für Technologie (KIT)
Umfang xii, 242 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 26.10.2022
Schlagwörter graph partitioning, hypergraph partitioning, shared-memory algorithms, algorithm engineering, multilevel algorithms, graph data structures, scalable algorithms
Referent/Betreuer Sanders, Peter
Çatalyürek, Ümit
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page