Mengenpackungsproblem

Das Mengenpackungsproblem (oft mit set-packing-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik.

Es fragt, ob zu einer endlichen Menge $U$ und $n$ Teilmengen $S_j$ von $U$ eine Anzahl von mindestens $k\le n$ paarweise disjunkter Teilmengen $S_j$ existieren.

Als Optimierungsproblem formuliert, wird eine Packung mit möglichst vielen Teilmengen $S_j$ gesucht oder, falls den Teilmengen $S_j$ Bewertungen $c_j$ zugeordnet sind, eine Packung mit maximaler Bewertung.

Das Mengenpackungsproblem gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard M. Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.

Siehe auch

• Mengenüberdeckungsproblem
• Mengenzerlegungsproblem

Literatur

• Vorlage:Literatur