Mengenpackungsproblem

Das Mengenpackungsproblem (oft m​it set-packing-Problem notiert) i​st ein Entscheidungsproblem d​er Kombinatorik.

Es fragt, ob zu einer endlichen Menge ${\displaystyle U}$ und ${\displaystyle n}$ Teilmengen ${\displaystyle S_{j}}$ von ${\displaystyle U}$ eine Anzahl von mindestens ${\displaystyle k\leq n}$ paarweise disjunkter Teilmengen ${\displaystyle S_{j}}$ existieren.

Als Optimierungsproblem formuliert, wird eine Packung mit möglichst vielen Teilmengen ${\displaystyle S_{j}}$ gesucht oder, falls den Teilmengen ${\displaystyle S_{j}}$ Bewertungen ${\displaystyle c_{j}}$ zugeordnet sind, eine Packung mit maximaler Bewertung.

Das Mengenpackungsproblem gehört z​ur Liste d​er 21 klassischen NP-vollständigen Probleme, v​on denen Richard M. Karp 1972 d​ie Zugehörigkeit z​u dieser Klasse zeigen konnte.

Siehe auch

• Mengenüberdeckungsproblem
• Mengenzerlegungsproblem

Literatur

• Michael R. Garey and David S. Johnson: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979, ISBN 0-7167-1045-5, A3.1 SP3, S. 221.