Next: MAXIMUM SET SPLITTING Up: Covering, Hitting, and Splitting Previous: MAXIMUM 3-DIMENSIONAL MATCHING Index

### MAXIMUM SET PACKING

- INSTANCE: Collection C of finite sets.

- SOLUTION: A set packing, i.e., a collection of disjoint sets .
- MEASURE: Cardinality of the set packing, i.e., |C'|.

- Good News: See MAXIMUM CLIQUE.

- Bad News: See MAXIMUM CLIQUE.

- Comment: Also called Maximum Hypergraph Matching. Equivalent to MAXIMUM CLIQUE under PTAS-reduction, where |C|=|V| [43]. Therefore approximation algorithms and nonapproximability results for MAXIMUM CLIQUE will carry over to MAXIMUM SET PACKING. In the weighted version of the problem the sets have positive weights and the objective is to maximize the total weight of the sets in the set packing. The equivalence to MAXIMUM CLIQUE holds also in the weighted case. Approximable within , where m is the cardinality of the underlying set [213]. This holds also in the weighted case [211].

  The problem MAXIMUM K-SET PACKING, the variation in which the cardinality of all sets in C are bounded from above by a constant , is APX-complete [265], and is approximable within for any [250]. Variation of MAXIMUM K-SET PACKING in which the sets have positive weights and the objective is to maximize the total weight of the sets in the set packing is approximable within for any [29] for and within 2(k+1)/3 [90].

  If the number of occurrences in C of any element is bounded by a constant B for the problem is APX-complete [69] and approximable within B, even for the weighted variation of the problem [231].

- Garey and Johnson: SP3

Next: MAXIMUM SET SPLITTING Up: Covering, Hitting, and Splitting Previous: MAXIMUM 3-DIMENSIONAL MATCHING Index