Set packing
Set packing is a classical NPcomplete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NPcomplete problems. Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint (in other words, no two of them share an element).
More formally, given a universe [math]\displaystyle{ \mathcal{U} }[/math] and a family [math]\displaystyle{ \mathcal{S} }[/math] of subsets of [math]\displaystyle{ \mathcal{U} }[/math], a packing is a subfamily [math]\displaystyle{ \mathcal{C}\subseteq\mathcal{S} }[/math] of sets such that all sets in [math]\displaystyle{ \mathcal{C} }[/math] are pairwise disjoint. The size of the packing is [math]\displaystyle{ \mathcal{C} }[/math]. In the set packing decision problem, the input is a pair [math]\displaystyle{ (\mathcal{U},\mathcal{S}) }[/math] and an integer [math]\displaystyle{ k }[/math]; the question is whether there is a set packing of size [math]\displaystyle{ k }[/math] or more. In the set packing optimization problem, the input is a pair [math]\displaystyle{ (\mathcal{U},\mathcal{S}) }[/math], and the task is to find a set packing that uses the most sets.
The problem is clearly in NP since, given k subsets, we can easily verify that they are pairwise disjoint in polynomial time.
The optimization version of the problem, maximum set packing, asks for the maximum number of pairwise disjoint sets in the list. It is a maximization problem that can be formulated naturally as an integer linear program, belonging to the class of packing problems.
Covering/packingproblem pairs  



Integer linear program formulation
The maximum set packing problem can be formulated as the following integer linear program.
maximize  [math]\displaystyle{ \sum_{S \in \mathcal S} x_S }[/math]  (maximize the total number of subsets)  
subject to  [math]\displaystyle{ \sum_{S\colon e \in S} x_S \leqslant 1 }[/math]  for all [math]\displaystyle{ e\in \mathcal U }[/math]  (selected sets have to be pairwise disjoint) 
[math]\displaystyle{ x_S \in \{0,1\} }[/math]  for all [math]\displaystyle{ S\in \mathcal S }[/math].  (every set is either in the set packing or not) 
Complexity
The set packing problem is not only NPcomplete, but its optimization version (general maximum set packing problem) has been proven as difficult to approximate as the maximum clique problem; in particular, it cannot be approximated within any constant factor.^{[1]} The best known algorithm approximates it within a factor of [math]\displaystyle{ O(\sqrt{U}) }[/math].^{[2]} The weighted variant can also be approximated as well.^{[3]}
However, the problem does have a variant which is more tractable: if we assume no subset exceeds k≥3 elements, the answer can be approximated within a factor of k/2 + ε for any ε > 0; in particular, the problem with 3element sets can be approximated within about 50%. In another more tractable variant, if no element occurs in more than k of the subsets, the answer can be approximated within a factor of k. This is also true for the weighted version.
Related problems
Equivalent problems
Hypergraph matching is equivalent to set packing: the sets correspond to the hyperedges.
The independent set problem is also equivalent to set packing  there is a onetoone polynomialtime reduction between them:
 Given a set packing problem on a collection [math]\displaystyle{ \mathcal{S} }[/math], build a graph where for each set [math]\displaystyle{ S \in \mathcal{S} }[/math] there is a vertex [math]\displaystyle{ v_S }[/math], and there is an edge between [math]\displaystyle{ v_S }[/math] and [math]\displaystyle{ v_T }[/math] iff [math]\displaystyle{ S \cap T \neq \varnothing }[/math]. Every independent set of vertices in the generated graph corresponds to a set packing in [math]\displaystyle{ \mathcal{S} }[/math].
 Given an independent vertex set problem on a graph [math]\displaystyle{ G(V,E) }[/math], build a collection of sets where for each vertex [math]\displaystyle{ v }[/math] there is a set [math]\displaystyle{ S_v }[/math] containing all edges adjacent to [math]\displaystyle{ v }[/math]. Every set packing in the generated collection corresponds to an independent vertex set in [math]\displaystyle{ G(V,E) }[/math].
This is also a bidirectional PTAS reduction, and it shows that the two problems are equally difficult to approximate.
Special cases
Graph matching is a special case of set packing in which the size of all sets is 2 (the sets correspond to the edges). In this special case, a maximumsize matching can be found in polynomial time.
3dimensional matching is a special case in which the size of all sets is 3, and in addition, the elements are partitioned into 3 colors and each set contains exactly one element of each color. This special case is still NPhard, though it has better constantfactor approximation algorithms than the general case.
In the set cover problem, we are given a family [math]\displaystyle{ \mathcal{S} }[/math] of subsets of a universe [math]\displaystyle{ \mathcal{U} }[/math], and the goal is to determine whether we can choose k sets that together contain every element of [math]\displaystyle{ \mathcal{U} }[/math]. These sets may overlap. The optimization version finds the minimum number of such sets. The maximum set packing need not cover every possible element.
In the exact cover problem, every element of [math]\displaystyle{ \mathcal{U} }[/math] should be contained in exactly one of the subsets. Finding such an exact cover is an NPcomplete problem, even in the special case in which the size of all sets is 3 (this special case is called exact 3 cover or X3C). However, if we create a singleton set for each element of S and add these to the list, the resulting problem is about as easy as set packing.
Karp originally showed set packing NPcomplete via a reduction from the clique problem.
See also: Packing in a hypergraph.
Notes
 ↑ Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), "On the complexity of approximating kset packing", Computational Complexity 15 (1): 20–39, doi:10.1007/s0003700602056. See in particular p. 21: "Maximum clique (and therefore also maximum independent set and maximum set packing) cannot be approximated to within [math]\displaystyle{ O(n^{1\epsilon}) }[/math] unless NP ⊂ ZPP."
 ↑ Halldórsson, Magnus M.; Kratochvíl, Jan; Telle, Jan Arne (1998). "Independent sets with domination constraints". 25th International Colloquium on Automata, Languages and Programming. 1443. SpringerVerlag. pp. 176–185.
 ↑ Halldórsson, Magnus M. (1999). "Approximations of weighted independent set and hereditary subset problems". 5th Annual International Conference on Computing and Combinatorics. 1627. SpringerVerlag. pp. 261–270.
References
 Maximum Set Packing, Viggo Kann.
 "set packing". Dictionary of Algorithms and Data Structures, editor Paul E. Black, National Institute of Standards and Technology. Note that the definition here is somewhat different.
 Steven S. Skiena. "Set Packing". The Algorithm Design Manual.
 Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. "Maximum Set Packing". A compendium of NP optimization problems. Last modified March 20, 2000.
 Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman. ISBN 9780716710455. A3.1: SP3, pg.221.
 Vazirani, Vijay V. (2001). Approximation Algorithms. SpringerVerlag. ISBN 9783540653677.
External links
 [1]: A Pascal program for solving the problem. From Discrete Optimization Algorithms with Pascal Programs by MacIej M. Syslo, ISBN 0132155095.
 Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination
 Solving packaging problem in PHP
 Optimizing ThreeDimensional Bin Packing
Original source: https://en.wikipedia.org/wiki/Set packing.
Read more 