Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.
Suppose we have 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 intersect).
More formally, given a universe and a family of subsets of, a packing is a subfamily of sets such that all sets in are pairwise disjoint. In the set packing decision problem, the input is a pair and an integer ; the question is whether there is a set packing of size or more. In the set packing optimization problem, the input is a pair, 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.
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, belongs to the class of packing problems, and its dual linear program is the set cover problem.
| Covering-packing dualities | |
| Covering problems | Packing problems |
|---|---|
| Minimum set cover | Maximum set packing |
| Minimum vertex cover | Maximum matching |
| Minimum edge cover | Maximum independent set |
Read more about Set Packing: Integer Linear Program Formulation, Example, Heuristics and Related Problems, Complexity
Famous quotes containing the words set and/or packing:
“When I married Humphrey I made up my mind to like sermons, and I set out by liking the end very much. That soon spread to the middle and the beginning, because I couldn’t have the end without them.”
—George Eliot [Mary Ann (or Marian)
“The good husband finds method as efficient in the packing of fire-wood in a shed, or in the harvesting of fruits in the cellar, as in Peninsular campaigns or the files of the Department of State.”
—Ralph Waldo Emerson (1803–1882)