Next: MINIMUM SET COVER
Up: Covering, Hitting, and Splitting
Previous: MAXIMUM SET PACKING
  Index
- 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
Viggo Kann
1999-04-22