Mengenzerlegungsproblem

Das Mengenzerlegungsproblem (oft mit set-partitioning-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik.

Es fragt, ob zu einer Menge ${\displaystyle U}$ und ${\displaystyle n}$ (nichtleeren) Teilmengen ${\displaystyle S_{j}}$ von ${\displaystyle U}$ und einer natürlichen Zahl ${\displaystyle k\leq n}$ eine Vereinigung von ${\displaystyle k}$ disjunkten Teilmengen ${\displaystyle S_{j}}$ existiert, die der Menge ${\displaystyle U}$ entspricht. (Für durch ${\displaystyle 1\leq j\leq n}$ indizierte ${\displaystyle S_{j}}$ gibt es dann eine ${\displaystyle k}$-elementige Menge ${\displaystyle K}$ von Zahlen ${\displaystyle i}$ mit ${\displaystyle 1\leq i\leq n}$, so dass ${\displaystyle \{\,S_{j}\mid j\in K\,\}}$ eine Zerlegung von ${\displaystyle U}$ ist.)

Als Optimierungsproblem formuliert, wird eine Zerlegung mit möglichst kleiner Anzahl der Teilmengen ${\displaystyle S_{j}}$ gesucht oder, falls den Teilmengen ${\displaystyle S_{j}}$ Kosten ${\displaystyle c_{j}}$ zugeordnet sind, eine Zerlegung mit geringsten Kosten.

• Problem der exakten Überdeckung
• Mengenüberdeckungsproblem
• Mengenpackungsproblem