Mengenzerlegungsproblem

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

Es fragt, ob zu einer Menge U und n 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 (Zerlegung).

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

• Mengenüberdeckungsproblem
• Mengenpackungsproblem