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

Alexander A. Ageev, Maxim SviridenkoESA 2000 · OpenReview

Abstract

An instance of Hypergraph Max k-Cut with given sizes of parts (or Hyp Max k-Cut with gsp) consists of a hypergraph H = (V, E), nonnegative weights ws defined on its edges S ∈ E, and k positive integers p 1,..., p k such that $$ \Sigma _{i = 1}^k pi = {\mathbf{ }}|V| $$ . It is required to partition the vertex set V into k parts X 1,..., Xk, with each part X i having size p i, so as to maximize the total weight of edges not lying entirely in any part of the partition. The version of the problem in which |X i may be arbitrary is known to be approximable within a factor of 0.72 of the optimum (Andersson and Engebretsen, 1998). The authors (1999) designed an 0.5-approximation for the special case when the hypergraph is a graph. The main result of this paper is that Hyp Max k-Cut with GSP can be approximated within a factor of min $$ \left\{ {\lambda _{|S|} :{\mathbf{ }}S \in E} \right\} $$ of the optimum, where $$ \lambda _r = 1 - (1 - 1/r)^r - (1/r)^r $$ .
BibTeX
@inproceedings{ageev2000approximation,
  author = {Alexander A. Ageev and Maxim Sviridenko},
  title = {{An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts}},
  booktitle = {ESA},
  year = {2000},
  url = {https://openreview.net/forum?id=nHcYLWMSLNMC},
}

Loading related content...

Figure