MAXIMUM SET SPLITTING

• INSTANCE: Collection C of subsets of a finite set S.
• SOLUTION: A partition of S into two disjoint subsets $S_1$ and $S_2$.
• MEASURE: Cardinality of the subsets in C that are not entirely contained in either $S_1$ or $S_2$.

  
  

• Good News: Approximable within 1.380 [20].
• Bad News: APX-complete [400].
• Comment: Also called Maximum Hypergraph Cut. Transformation from MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY. Variation in which all subsets contain the same number of elements, k, is approximable within 1.138 for $k\le 3$ and $1/(1-2^{1-k})$ for $k\ge 4$, and not approximable within 1.013 for $k\le 3$ and $1+O(k^{-3}2^{-k})$ for any $\varepsilon >0$ for $k\ge 4$ [287]. It admits a PTAS if $\vert C\vert=\Theta(\vert S\vert^k)$ [39].
• Garey and Johnson: SP4