SP2 M AXIMUM S ET P ACKING

       
• I NSTANCE : Collection C of finite sets.
• S OLUTION : A set packing, i.e., a collection of disjoint sets .
• M EASURE : Cardinality of the set packing, i.e., |C'| .

• Good News: See M AXIMUM C LIQUE .
• Bad News: See M AXIMUM C LIQUE .
• Comment: Also called Maximum Hypergraph Matching .       Equivalent to M AXIMUM C LIQUE under PTAS-reduction, where |C|=|V| [ 27 ]. Therefore approximation algorithms and nonapproximability results for M AXIMUM C LIQUE will carry over to M AXIMUM S ET P ACKING . The problem M AXIMUM K -S ET P ACKING , the variation in which the cardinality of all sets in C are bounded from above by a constant , is A PX -complete [ 198 ], and is approximable within for any [ 182 ].   Still A PX -complete when the number of occurrences in C of any element is bounded by a constant B for [ 46 ]]. Approximable within B if the number of occurrences in C of any element is bounded by B , even for the weighted variation of the problem [ 167 ].
• Garey and Johnson: SP3