Search papers, labs, and topics across Lattice.
This paper introduces IMPart, a novel memetic framework that integrates recombination and mutation operations directly into the uncoarsening phase of a multi-level hypergraph partitioning approach. By transforming local searches into a collaborative search mechanism, IMPart significantly enhances the ability to escape local optima and explore the global solution space, particularly for large-k hypergraph partitioning. Experimental results demonstrate that IMPart outperforms existing hypergraph partitioners, achieving higher-quality solutions across multiple benchmarks.
IMPart redefines hypergraph partitioning by seamlessly integrating memetic operations, leading to superior solution quality for large-k scenarios.
The problem of k-way hypergraph partitioning is fundamental with significant applications in various fields, including VLSI design and scientific computing. State-of-the-art hypergraph partitioners commonly employ a multi-level framework encompassing coarsening, initial partitioning, uncoarsening, and refinement phases. However, many existing methods do not scale well to problems requiring a large number of partitions (i.e., large k). In pursuit of exceptionally high solution quality, existing memetic approaches often execute their two key operations, recombination and mutation, by invoking separate, standalone multi-level partitioners. This design choice, however, renders them significantly more time-consuming than standard multi-level partitioners. To make such memetic approaches more practical, we propose an advanced memetic framework, IMPart, which introduces novel recombination and mutation operators and integrates them directly into the uncoarsening phase of a single multi-level framework. This transforms the local searches of different granularities in the traditional multi-level framework into a sophisticated, collaborative search. Experimental results on multiple standard benchmarks demonstrate our framework more effectively escapes local optima and explores the global solution space for higher-quality solutions, substantially outperforming all existing hypergraph partitioners for large-$k$-way hypergraph partitioning. Our framework highlights a new paradigm for the development of advanced hypergraph partitioners.
