  We study the balanced $k$-way hypergraph partitioning problem, with a special
focus on its practical applications to manycore scheduling. Given a hypergraph
on $n$ nodes, our goal is to partition the node set into $k$ parts of size at
most $(1+\epsilon)\cdot \frac{n}{k}$ each, while minimizing the cost of the
partitioning, defined as the number of cut hyperedges, possibly also weighted
by the number of partitions they intersect. We show that this problem cannot be
approximated to within a $n^{1/\text{poly} \log\log n}$ factor of the optimal
solution in polynomial time if the Exponential Time Hypothesis holds, even for
hypergraphs of maximal degree 2. We also study the hardness of the partitioning
problem from a parameterized complexity perspective, and in the more general
case when we have multiple balance constraints.
  Furthermore, we consider two extensions of the partitioning problem that are
motivated from practical considerations. Firstly, we introduce the concept of
hyperDAGs to model precedence-constrained computations as hypergraphs, and we
analyze the adaptation of the balanced partitioning problem to this case.
Secondly, we study the hierarchical partitioning problem to model hierarchical
NUMA (non-uniform memory access) effects in modern computer architectures, and
we show that ignoring this hierarchical aspect of the communication cost can
yield significantly weaker solutions.
