Traditional hypergraph partitioning algorithms compute a bisection a graph such that the number of hyperedges that are cut by the partitioning is minimized and each partition has an equal number of vertices. The task of minimizing the cut can be considered as the objective and the requirement that the partitions will be of the same size can be considered as the constraint.
In this talk, we present hypergraph partitioning algorithms that are based on the multilevel paradigm. In the multilevel paradigm, a sequence of successively coarser hypergraphs is constructed. A partitioning of the smallest hypergraph is computed and it is used to obtain a partitioning of the original hypergraph by successively projecting and refining the bisection to the next level finer hypergraph. We have developed new hypergraph coarsening strategies that are well suited for hypergraphs arising in VLSI circuit domains. Our experiments show that our multilevel hypergraph partitioning algorithm produces high quality partitioning in a relatively small amount of time.
We also extend the partitioning problem by incorporating an arbitrary number of balancing constraints. In our formulation, a vector of weights is assigned to each vertex, and the goal is to produce a bisection such that the partitioning satisfies a balancing constraint associated with each weight, while attempting to minimize the cut. We present new multi-constraint hypergraph partitioning algorithms that are based on the multilevel partitioning paradigm. We experimentally evaluate the effectiveness of our multi-constraint partitioners on a variety of synthetically generated problems.
Speaker bio
Presentation (PDF File)
Copyright. All Rights Reserved.