Mengenzerlegungsproblem
Das Mengenzerlegungsproblem (oft mit set-partitioning-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik.
Es fragt, ob zu einer Menge <math>U</math> und <math>n</math> (nichtleeren) Teilmengen <math>S_j</math> von <math>U</math> und einer natürlichen Zahl <math>k \le n</math> eine Vereinigung von <math>k</math> disjunkten Teilmengen <math>S_j</math> existiert, die der Menge <math>U</math> entspricht. (Für durch <math>1\leq j\leq n</math> indizierte <math>S_j</math> gibt es dann eine <math>k</math>-elementige Menge <math>K</math> von Zahlen <math>i</math> mit <math>1\leq i\leq n</math>, so dass <math>\{\,S_j\mid j\in K\,\}</math> eine Zerlegung von <math>U</math> ist.)
Als Optimierungsproblem formuliert, wird eine Zerlegung mit möglichst kleiner Anzahl der Teilmengen <math>S_j</math> gesucht oder, falls den Teilmengen <math>S_j</math> Kosten <math>c_j</math> zugeordnet sind, eine Zerlegung mit geringsten Kosten.