Bulk packing problem

The set packing (often with set-packing problem listed) is a decision problem of combinatorics .

It asks whether a number of at least pairwise disjoint subsets exist for a finite set and subsets of . ${\displaystyle U}$ ${\displaystyle n}$ ${\displaystyle S_{j}}$ ${\displaystyle U}$ ${\displaystyle k\leq n}$ ${\displaystyle S_{j}}$

Formulated as an optimization problem, a pack with as many subsets as possible is sought or, if ratings are assigned to the subsets , a pack with a maximum rating. ${\displaystyle S_{j}}$ ${\displaystyle S_{j}}$ ${\displaystyle c_{j}}$

The set packing problem belongs to the list of 21 classical NP-complete problems , of which Richard M. Karp was able to show in 1972 that they belong to this class .

See also

• Quantity coverage problem
• Set decomposition problem

literature

• Michael R. Garey and David S. Johnson: Computers and Intractability. A Guide to the Theory of NP Completeness . WH Freeman, 1979, ISBN 0-7167-1045-5 , A3.1 SP3, pp. 221 .