  Despite there being significant work on developing spectral, and metric
embedding based approximation algorithms for hypergraph generalizations of
conductance, little is known regarding the approximability of hypergraph
partitioning objectives beyond this.
  This work proposes algorithms for a general model of hypergraph partitioning
that unifies both undirected and directed versions of many well-studied
partitioning objectives. The first contribution of this paper introduces
polymatroidal cut functions, a large class of cut functions amenable to
approximation algorithms via metric embeddings and routing multicommodity
flows. We demonstrate an $O(\sqrt{\log n})$-approximation, where $n$ is the
number of vertices in the hypergraph, for these problems by rounding
relaxations to metrics of negative-type.
  The second contribution of this paper generalizes the cut-matching game
framework of Khandekar et. al. to tackle polymatroidal cut functions. This
yields the first almost-linear time $O(\log n)$-approximation algorithm for
standard versions of undirected and directed hypergraph partitioning. A
technical consequence of our construction is that a cut-matching game which
greatly relaxes the set of allowed actions for both players can be used to
partition hypergraphs with negligible impact on the approximation ratio. We
believe this to be of independent interest.
