Partitioning Hypergraphs is Hard: Models, Inapproximability, and Applications

Pál András Papp, Georg Anegg, A. N. Yzelman

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…