  The balanced hypergraph partitioning problem (HGP) is to partition the vertex
set of a hypergraph into k disjoint blocks of bounded weight, while minimizing
an objective function defined on the hyperedges. Whereas real-world
applications often use vertex and edge weights to accurately model the
underlying problem, the HGP research community commonly works with unweighted
instances.
  In this paper, we argue that, in the presence of vertex weights, current
balance constraint definitions either yield infeasible partitioning problems or
allow unnecessarily large imbalances and propose a new definition that
overcomes these problems. We show that state-of-the-art hypergraph partitioners
often struggle considerably with weighted instances and tight balance
constraints (even with our new balance definition). Thus, we present a
recursive-bipartitioning technique that is able to reliably compute balanced
(and hence feasible) solutions. The proposed method balances the partition by
pre-assigning a small subset of the heaviest vertices to the two blocks of each
bipartition (using an algorithm originally developed for the job scheduling
problem) and optimizes the actual partitioning objective on the remaining
vertices. We integrate our algorithm into the multilevel hypergraph partitioner
KaHyPar and show that our approach is able to compute balanced partitions of
high quality on a diverse set of benchmark instances.
