Set decomposition problem

The amount decomposition problem (often with set-partitioning problem listed) is a decision problem of combinatorics .

It asks whether for a set and ( non-empty ) subsets of and a natural number there exists a union of disjoint subsets that corresponds to the set . (For indexed by there is then a -element set of numbers with such that is a decomposition of .) ${\displaystyle U}$ ${\displaystyle n}$ ${\displaystyle S_{j}}$ ${\displaystyle U}$ ${\displaystyle k\leq n}$ ${\displaystyle k}$ ${\displaystyle S_{j}}$ ${\displaystyle U}$ ${\displaystyle 1\leq j\leq n}$ ${\displaystyle S_{j}}$ ${\displaystyle k}$ ${\displaystyle K}$ ${\displaystyle i}$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle \{\,S_{j}\mid j\in K\,\}}$ ${\displaystyle U}$

Formulated as an optimization problem, a breakdown with the smallest possible number of subsets is sought or, if costs are assigned to the subsets , a breakdown with the lowest possible costs. ${\displaystyle S_{j}}$ ${\displaystyle S_{j}}$ ${\displaystyle c_{j}}$

See also

• Exact overlap problem
• Quantity coverage problem
• Bulk packing problem