Multilevel k-Wege-Hypergraph-Partitionierung

In diesem Papier präsentieren wir einen neuen Multilevel k-Wege-Hypergraph-Partitionierungsalgorithmus, der die bestehende State-of-the-Art K-PM/LR-Algorithmus für Mehrfachpartitionierung erheblich übertrifft, sowohl bei der Optimierung lokaler als auch globaler Ziele. Experimente auf dem ISPD98 Benchmark-Suite zeigen, dass die von unserem Schema produzierten Partitionen im Durchschnitt 15 % bis 23 % besser sind als die vom K-PM/LR-Algorithmus, sowohl in Bezug auf den Hyperedge-Schnitt als auch auf die (K-1)-Metrik. Darüber hinaus ist unser Algorithmus erheblich schneller und benötigt 4 bis 5 Mal weniger Zeit als die vom K-PM/LR benötigte Zeit.