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\leq n$ eine Vereinigung von $k$ disjunkten Teilmengen $S_{j}$ existiert, die der Menge $U$ entspricht. (Für durch $1\leq j\leq n$ indizierte $S_{j}$ gibt es dann eine $k$-elementige Menge $K$ von Zahlen $i$ mit $1\leq i\leq 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