An Approximation Algorithm for Hypergraph Max  -Cut with Given Sizes
of Parts
Alexander A. Ageev
December 1999 |
|
An Approximation Algorithm for Hypergraph Max -Cut with Given Sizes
of Parts
Alexander A. Ageev
December 1999 |
Abstract:
In this paper we demonstrate that the pipage rounding technique
can be applied to the Hypergraph Max
-Cut problem with given sizes of
parts. We present a polynomial time approximation algorithm and prove that
its performance guarantee is tightAvailable as PostScript, PDF, DVI. |