Mengenzerlegungsproblem

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

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

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

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

• Komplexitätstheorie
• Kombinatorische Optimierung