An Approximation Algorithm for Hypergraph Max $k$-Cut with Given Sizes of Parts

Alexander A. Ageev
Maxim I. Sviridenko

December 1999


In this paper we demonstrate that the pipage rounding technique can be applied to the Hypergraph Max $k$-Cut problem with given sizes of parts. We present a polynomial time approximation algorithm and prove that its performance guarantee is tight

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.