Evolutionary n-level Hypergraph Partitioning with Adaptive Coarsening
share
Hypergraph partitioning is an NP-hard problem that occurs in many computer science applications where it is necessary to reduce large problems into a number of smaller, computationally tractable sub-problems, with the consequent desire that these should be as independent as possible to reduce the inevitable side-effects of not taking a global approach. Current techniques use a multilevel approach that first coarsens the hypergraph into a smaller set of representative super nodes, partitions these, prior to uncoarsening to achieve a final set of partitions for the full hypergraph. We develop evolutionary approaches for the initial (high-level) partitioning problem, and show that meta-heuristic global search outperforms existing state-of-the-art frameworks that use a portfolio of simpler local search algorithms. We explore the coarsening spectrum of possible initial hypergraphs to identify the optimum landscape in which to achieve the lowest final cut-sizes and introduce an adaptive coarsening scheme using the characteristics of the hypergraph as it is coarsened to identify initial hypergraphs which maximise compression and information content.
READ FULL TEXT