Multilevel k‐way Hypergraph Partitioning

In this paper, we present a new multilevel k-way hypergraph parti- tioning algorithm that substantially outperforms the existing state- of-the-art K-PM/LR algorithm for multi-way partitioning. both for optimizing local as well as global objectives. Experiments on the ISPD98 benchmark suite show that the partitionings produced by our scheme are on the average 15% to 23% better than those pro- duced by the K-PM/LR algorithm, both in terms of the hyperedge cut as well as the K 1 metric. Furthermore, our algorithm is sig- nificantly faster, requiring 4 to 5 times less time than that required by K-PM/LR.