Next: MINIMUM SET COVER Up: Covering, Hitting, and Splitting Previous: MAXIMUM SET PACKING Index

### MAXIMUM SET SPLITTING

- INSTANCE: Collection C of subsets of a finite set S.

- SOLUTION: A partition of S into two disjoint subsets S1 and S2.

- MEASURE: Cardinality of the subsets in C that are not entirely contained in either S1 or S2.

- Good News: Approximable within 1.380 [19].

- Bad News: APX-complete [378].

- 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 1/(1-21-k) for , and not approximable within 1.013 for and 1+O(k-32-k) for any for [272]. It admits a PTAS if [37].

- Garey and Johnson: SP4