Mengenpackungsproblem

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

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

Als Optimierungsproblem formuliert, wird eine Packung mit möglichst vielen Teilmengen ${\displaystyle S_{j}}${\displaystyle S_{j}} gesucht oder, falls den Teilmengen ${\displaystyle S_{j}}${\displaystyle S_{j}} Bewertungen ${\displaystyle c_{j}}${\displaystyle 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.

• Mengenüberdeckungsproblem
• Mengenzerlegungsproblem

• 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. 

• Komplexitätstheorie
• Kombinatorische Optimierung