SP3 M AXIMUM S ET S PLITTING

     
• I NSTANCE : Collection C of subsets of a finite set S .
• S OLUTION : A partition of S into two disjoint subsets and .
• M EASURE : Cardinality of the subsets in C that are not entirely contained in either or .

• Good News: Approximable within 2.
• Bad News: A PX -complete [ 290 ].
• Comment: Also called Maximum Hypergraph Cut .       Transformation from M AXIMUM N OT -A LL -E QUAL 3-S ATISFIABILITY . 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 [ 205 ]. It admits a PTAS if [ 24 ].
• Garey and Johnson: SP4