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

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 Ergebnis oft von zufälligen Entscheidungen ab, welche der Algorithmus selbst trifft [15, 31, 36]. ... mehrFlussbasierende Ansätze sind nicht bewegungbasiert und finden einen globalen minimalen Schnitt, welcher zwei Knoten s und t eines Graphen trennt [18]. Unser Framework ist durch die Arbeit von Sanders und Schulz [44] inspiriert. Diese integrierten eine flussbasierende Heuristik erfolgreich in Ihren Multilevel Graph Partitionierer. Wir generalisieren viele Ihrer Ideen, sodass sie im Multilevel Hypergraph Partitionierung-Kontext anwendbar sind. Wir entwickeln mehrere Techniken, um das aktuelle Hypergraph Flussnetzwerk zu verkleinern, welche die resultierende Problemgröße im Vergleich zu der aktuellen Representation [33], um den Faktor 2 reduziert. Zusätzlich zeigen wir, wie ein Flussproblem auf einem Subhypergraphen konfiguriert werden kann, sodass das eine Max-Flow-Min-Cut Berechnung eine bessere Qualität erzielt, als die Modellierung von Sanders und Schulz. Am Ende haben wir unsere Arbeit als Verbesserungsstrategie in den n-level Hypergraph Partitionierer KaHyPar integriert [25]. Wir haben unser Framework auf 3216 verschiedenen Instanzen getestet. Im Vergleich mit 5 verschiedenen Systemen erzielt unsere neue Konfiguration, auf 73% der Instanzen, die besten Ergebnisse. Im Vergleich zu der aktuellen Variante von KaHyPar ist die Qualität der Lösungen um 2.5% gestiegen, während die Laufzeit lediglich um den Faktor 2 langsamer ist. Jedoch hat unser Algorithmus eine vergleichbare Laufzeit mit hMetis und erzielt auf 84% der Instanzen bessere Ergebnisse.

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 approaches are not move-based and they are able to find a global minimum cut separating two vertices s and t [18]. ... mehrOur framework is inspired by the work of Sanders and Schulz [44] who successfully integrate a flow-based refinement algorithm into a multilevel graph partitioner. We generalize many ideas such that they are applicable in the multilevel hypergraph partitioning context. We develop several techniques to sparsify the hypergraph flow network, which reduces the resulting problem size by a factor of 2 on average compared to the state-of-the-art representation [33]. Additionally, we show how to configure a flow problem on a subhypergraph such that the quality achievable with a Max-Flow-Min-Cut computation is significantly better than with the modeling approach of Sanders and Schulz. Finally, we integrate our work as refinement strategy into the n-level hypergraph partitioner KaHyPar [25]. We tested our framework on a large benchmark set with 3216 instances. In comparison to 5 different systems, our new configuration outperforms the tested stateof-the-art hypergraph partitioners on 73% of the instances. In comparison to the latest version of KaHyPar, our new approach improves quality by 2.5% while only incurring a performance slowdown by a factor of 2. However, our algorithm is still as fast as the direct k-way version of hMetis and outperforms it on 84% of the benchmarks