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

*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 and for , and not approximable within 1.013 for and for any for [287]. It admits a PTAS if [39].*Garey and Johnson:*SP4