Set packing is a classical

Maximum Set Packing

Viggo Kann. *

. ''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,

Maximum Set Packing

''A compendium of NP optimization problems''

Last modified March 20, 2000. * A3.1: SP3, pg.221. *

A Pascal program for solving the problem. From ''Discrete Optimization Algorithms with Pascal Programs'' by MacIej M. Syslo, .

Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination

Optimizing Three-Dimensional Bin Packing

{{Packing problem Combinatorics NP-complete problems

NP-complete
In computational complexity theory
Computational complexity theory focuses on classifying computational problem
In theoretical computer science
An artistic representation of a Turing machine. Turing machines are used to model general computi ...

problem in computational complexity theory
Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by ...

and combinatorics
Combinatorics is an area of mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geom ...

, and was one of Karp's 21 NP-complete problemsIn computational complexity theory
Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A ...

.
Suppose one has a finite set
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

''S'' and a list of subset
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

s of ''S''. Then, the set packing problem asks if some ''k'' subsets in the list are pairwise (in other words, no two of them share an element).
More formally, given a universe $\backslash mathcal$ and a family $\backslash mathcal$ of subsets of $\backslash mathcal$,
a ''packing'' is a subfamily $\backslash mathcal\backslash subseteq\backslash mathcal$ of sets such that all sets in $\backslash mathcal$ are pairwise disjoint. The size of the packing is $,\; \backslash mathcal,$. In the set packing decision problem
In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding whether a given natural number is prime. Anot ...

, the input is a pair $(\backslash mathcal,\backslash mathcal)$ and an integer $k$; the question is whether
there is a set packing of size $k$ or more. In the set packing optimization problem
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

, the input is a pair $(\backslash mathcal,\backslash mathcal)$, 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
In computer science
Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application.
Computer science is the study of com ...

.
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
An integer programming problem is a mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of ...

, belonging to the class of packing problems
Packing problems are a class of optimization problem
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), a ...

.
Integer linear program formulation

The maximum set packing problem can be formulated as the followinginteger linear program
An integer programming problem is a mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of ...

.
Complexity

The set packing problem is not only NP-complete, but its optimization version (general maximum set packing problem) has been proven as difficult to approximate as themaximum clique problem
In computer science, the clique problem is the computational problem of finding clique (graph theory), cliques (subsets of vertices, all Adjacent (graph theory), adjacent to each other, also called complete graph, complete Glossary of graph theo ...

; in particular, it cannot be approximated within any constant factor. The best known algorithm approximates it within a factor of $O(\backslash sqrt)$.
The weighted variant can also be approximated as well.
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 3-element 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 one-to-one polynomial-time reduction between them: * Given a set packing problem on a collection $\backslash mathcal$, build a graph where for each set $S\; \backslash in\; \backslash mathcal$ there is a vertex $v\_S$, and there is an edge between $v\_S$ and $v\_T$ iff $S\; \backslash cap\; T\; \backslash neq\; \backslash varnothing$. Every independent set of vertices in the generated graph corresponds to a set packing in $\backslash mathcal$. * Given an independent vertex set problem on a graph $G(V,E)$, build a collection of sets where for each vertex $v$ there is a set $S\_v$ containing all edges adjacent to $v$. Every set packing in the generated collection corresponds to an independent vertex set in $G(V,E)$. This is also a bidirectionalPTAS reduction In computational complexity theory, a PTAS reduction is an approximation-preserving reduction that is often used to perform Reduction (complexity), reductions between solutions to optimization problems. It preserves the property that a problem has a ...

, and it shows that the two problems are equally difficult to approximate.
Special cases

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 maximum-size matching can be found in polynomial time. 3-dimensional 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 NP-hard, though it has better constant-factor approximation algorithms than the general case.Other related problems

In the set cover problem, we are given a family $\backslash mathcal$ of subsets of a universe $\backslash mathcal$, and the goal is to determine whether we can choose ''k'' sets that together contain every element of $\backslash mathcal$. 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 $\backslash mathcal$ should be contained in ''exactly one'' of the subsets. Finding such an exact cover is anNP-complete
In computational complexity theory
Computational complexity theory focuses on classifying computational problem
In theoretical computer science
An artistic representation of a Turing machine. Turing machines are used to model general computi ...

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
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

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 NP-complete via a reduction from the clique problem.
See also: Packing in a hypergraph.
Notes

References

Maximum Set Packing

Viggo Kann. *

. ''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
Marek KarpinskiMarek Karpinski Biography

at the Hausdorff Center for Mathematics, Excel ...

and Gerhard Woeginger.at the Hausdorff Center for Mathematics, Excel ...

Maximum Set Packing

''A compendium of NP optimization problems''

Last modified March 20, 2000. * A3.1: SP3, pg.221. *

External links

A Pascal program for solving the problem. From ''Discrete Optimization Algorithms with Pascal Programs'' by MacIej M. Syslo, .

Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination

Optimizing Three-Dimensional Bin Packing

{{Packing problem Combinatorics NP-complete problems