KIT | KIT-Bibliothek | Impressum | Datenschutz

Quality Hypergraph Partitioning via Max-Flow-Min-Cut Computations

Heuer, Tobias

Abstract:
In dieser Arbeit wird ein Framework basierend auf Max-Flow-Min-Cut Berechnungen vorgestellt, zur Verbesserung einer balancierten k-teilige Aufteilung eines Hypergraphen. Aktuell werden Varianten des FM Algorithmus [17] in allen modernen Multilevel Hypergraph Partitionierer als lokaler Suchalgorithmus verwendet. Solche bewegungsbasierenden Heuristiken haben den Nachteil, dass sie nur lokale Informationen über die Problemstruktur in die Berechnungen miteinfließen lassen. Wenn viele Knotenbewegungen den selben Einfluss auf die Lösungsqualität haben, dann hängt das Ergebni ... mehr

Abstract (englisch):
In this thesis, we introduce a framework based on Max-Flow-Min-Cut computations for improving balanced k-way partitions of hypergraphs. Currently, variations of the FM heuristic [17] are used as local search algorithms in all state-of-the-art multilevel hypergraph partitioners. Such move-based heuristics have the disadvantage that they only incorporate local information about the problem structure and if many moves of vertices have an equal impact on the solution quality, the outcome mainly depends on random choices made within the algorithm [15, 31, 36]. Flowbased app ... mehr

Open Access Logo


Volltext §
DOI: 10.5445/IR/1000083200
Veröffentlicht am 19.06.2018
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2018
Sprache Englisch
Identifikator urn:nbn:de:swb:90-832002
KITopen-ID: 1000083200
Verlag KIT, Karlsruhe
Umfang 64 S.
Abschlussart Abschlussarbeit - Master
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page