Multilevel Algorithms for Multi-Constraint Hypergraph Partitioning.

摘要

Traditional hypergraph partitioning algorithms compute a bisection of 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 paper, the author extends the partitioning problem by incorporating an arbitrary number of balancing constraints. In this 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. The author presents new multi- constraint hypergraph partitioning algorithms that are based on the multilevel partitioning paradigm. He experimentally evaluates the effectiveness of the multi-constraint partitioners on a variety of synthetically generated problems.