Metraipolis › archive › dc_daa72f2174b0

Set packing — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Set_packing
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T17:23:15.465Z
SHA-256 of the archived text
7060ff3202084e3f37087d53bd4866521b1ef9c9df4889871e0a33abb3411f6e
Stable URL of this page
https://metraipolis.com/documento/dc_daa72f2174b0

How to cite

Set packing — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Set_packing (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_daa72f2174b0 (Metraipolis archive dc_daa72f2174b0, sha256 7060ff3202084e3f37087d53bd4866521b1ef9c9df4889871e0a33abb3411f6e)
BibTeX
@misc{dcdaa72f2174b0,
  title = {Set packing — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Set_packing},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_daa72f2174b0; sha256 7060ff3202084e3f37087d53bd4866521b1ef9c9df4889871e0a33abb3411f6e},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Set_packing. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 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 U {\displaystyle {\mathcal {U}}} and a family S {\displaystyle {\mathcal {S}}} of subsets of U {\displaystyle {\mathcal {U}}} , a packing is a subfamily C ⊆ S {\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}} of sets such that all sets in C {\displaystyle {\mathcal {C}}} are pairwise disjoint. The size of the packing is | C | {\displaystyle |{\mathcal {C}}|} . In the set packing decision problem, the input is a pair ( U , S ) {\displaystyle ({\mathcal {U}},{\mathcal {S}})} and an integer t {\displaystyle t} ; the question is whether there is a set packing of size t {\displaystyle t} or more. In the set packing optimization problem, the input is a pair ( U , S ) {\displaystyle ({\mathcal {U}},{\mathcal {S}})} , and the task is to find a set packing that uses the most sets. The problem is clearly in NP since, given t {\displaystyle t} 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.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Combinatorics»).
Fonte: Wikipedia in inglese, voce «Set packing» — https://en.wikipedia.org/wiki/Set_packing
Wikidata Q475603 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q475603
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Set_packing?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1369239018, consultata il 2026-10-07T16:54:30.488Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 5e255b35cafa086a5938e58c5954dd6e935481508b350aba2ad2e4a2b5b4f206