# Evolutionary $n$ -Level Hypergraph Partitioning With Adaptive Coarsening

@article{Preen2019Evolutionary, title={Evolutionary \$n\$ -Level Hypergraph Partitioning With Adaptive Coarsening}, author={Richard John Preen and Jim E. Smith}, journal={IEEE Transactions on Evolutionary Computation}, year={2019}, volume={23}, pages={962-971} }

Hypergraph partitioning (HGP) 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 subproblems. Current techniques use a multilevel approach wherein an initial partitioning is performed after compressing the hypergraph to a predetermined level. This level is typically chosen to produce very coarse hypergraphs in which heuristic algorithms are fast and effective. This paper… Expand

#### Supplemental Code

Github Repo

KaHyPar (Karlsruhe Hypergraph Partitioning) is a multilevel hypergraph partitioning framework providing direct k-way and recursive bisection based partitioning algorithms that compute solutions of very high quality.

#### 5 Citations

High-Quality Hypergraph Partitioning

- Computer Science
- ArXiv
- 2020

KaHyPar, already without the memetic component, computes better solutions than all competing algorithms for both the cut-net and the connectivity metric, while being faster than Zoltan-AlgD and equally fast as hMETIS. Expand

Dynamic Partition of Large Graphs Combining Local Nodes Exchange with Directed Dynamic Maintenance

- Computer Science
- WISA
- 2020

A processing technique combining initial graph partition with incremental dynamic maintenance with directed dynamic maintenance strategy to improve the efficiency of dynamic graph partition and optimization adjustment mechanism to eliminate redundant modification and reduce computing cost. Expand

An evolutionary approach to implement logic circuits on three dimensional FPGAs

- Computer Science
- Expert Syst. Appl.
- 2021

A complete Computer Aided Design (CAD) flow to implement an arbitrary logic circuit on 3D FPGA is proposed and simulation results show more than 60%, 65%, and 23% reduction in TSV count, heat transfer performance, and area respectively, along with 4% increase in critical path delay. Expand

Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows

- Computer Science
- Swarm Evol. Comput.
- 2021

A memetic algorithm with efficient local search and extended neighborhood, dubbed MATE, for solving the vehicle routing problem with simultaneous pickup-delivery and time windows, which consistently outperforms all the state-of-the-art algorithms. Expand

#### References

SHOWING 1-10 OF 64 REFERENCES

Multilevel hypergraph partitioning: applications in VLSI domain

- Computer Science
- IEEE Trans. Very Large Scale Integr. Syst.
- 1999

A new hypergraph-partitioning algorithm that is based on the multilevel paradigm, which scales very well for large hypergraphs and produces high-quality partitioning in a relatively small amount of time. Expand

k-way Hypergraph Partitioning via n-Level Recursive Bisection

- Mathematics, Computer Science
- ALENEX
- 2016

A multilevel algorithm for hypergraph partitioning that contracts the vertices one at a time that forms the basis of the KaHyPar (Karlsruhe Hypergraph Partitioning) framework, which achieves significantly smaller cuts than hMetis and PaToH. Expand

Parallel algorithms for hypergraph partitioning

- Computer Science
- 2006

This thesis presents the first parallel hypergraph partitioning algorithms, enabling both partitioning of much larger hypergraphs, and computation of partitions with significantly reduced runtimes. Expand

Parallel multilevel algorithms for hypergraph partitioning

- Computer Science
- J. Parallel Distributed Comput.
- 2008

This paper presents parallel multilevel algorithms for the hypergraph partitioning problem, in particular, for parallel coarsening, parallel greedy k-way refinement and parallel multi-phase refinement and derives the isoefficiency function for these algorithms using an asymptotic theoretical performance model. Expand

Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure

- Mathematics, Computer Science
- SEA
- 2017

An improved coarsening process for multilevel hypergraph partitioning that incorporates global information about the community structure is presented that significantly improves the solutions found by the initial partitioning algorithm and consistently improves overall solution quality. Expand

A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

- Computer Science
- SIAM J. Sci. Comput.
- 1998

This work presents a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of theSize of the final partition obtained after multilevel refinement, and presents a much faster variation of the Kernighan--Lin (KL) algorithm for refining during uncoarsening. Expand

Memetic multilevel hypergraph partitioning

- Computer Science, Mathematics
- GECCO
- 2018

This work develops the first multilevel memetic algorithm to tackle hypergraph partitioning, and performs a wide range of experiments on a benchmark set containing instances from application areas such as VLSI, SAT solving, social networks, and scientific computing. Expand

A Multilevel Memetic Approach for Improving Graph k-Partitions

- Mathematics, Computer Science
- IEEE Transactions on Evolutionary Computation
- 2011

A highly effective multilevel memetic algorithm, which integrates a new multiparent crossover operator and a powerful perturbation-based tabu search algorithm that performs far better than any of the existing graph partitioning algorithms in terms of solution quality. Expand

A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph-Partitioning

- Mathematics, Computer Science
- J. Glob. Optim.
- 2004

An evolutionary search algorithm for finding benchmark partitions using a multilevel heuristic algorithm to provide an effective crossover and it is demonstrated that this method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages. Expand

Hypergraph partitioning in the cloud

- Computer Science
- 2016

This thesis proposes two multi-level hypergraph partitioning algorithms based on rough set clustering techniques and provides a trade-off between global and local vertex clustering decisions, which achieves better scalability than the state-of-the-art parallel hyper graph partitioner in the Zoltan tool on a set of benchmarks. Expand