Mengenzerlegungsproblem

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

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

Als Optimierungsproblem formuliert, wird eine Zerlegung mit möglichst kleiner Anzahl der Teilmengen $S_j$ gesucht oder, falls den Teilmengen $S_j$ Kosten $c_j$ zugeordnet sind, eine Zerlegung mit geringsten Kosten.

Siehe auch

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