Multilevel Memetic Hypergraph Partitioning With Greedy Recombination

Abstract

The Hypergraph Partitioning (HGP) problem is a well-studied problem that finds applications in a variety of domains. In several application domains, such as the VLSI design and database migration planning, the quality of the solution is more of a concern than the running time of the algorithm. In this work, we introduce novel problem-specific recombination and mutation operators and develop a new multilevel memetic algorithm by combining these operators with kKaHyPar-E. The performance of our algorithm is compared with the state-of-the-art HGP algorithms on 150 real-life instances taken from the benchmark sets used in the literature. The experiments reveal that our algorithm outperforms all others, and finds the best solutions in 112, 115, and 125 instances in 2, 4, and 8 hours, respectively. © 2022 Owner/Author.