Das Mengenpackungsproblem (oft mit set-packing-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik.
Es fragt, ob zu einer endlichen Menge und Teilmengen von eine Anzahl von mindestens paarweise disjunkter Teilmengen existieren.
Als Optimierungsproblem formuliert, wird eine Packung mit möglichst vielen Teilmengen gesucht oder, falls den Teilmengen Bewertungen 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 Bearbeiten
Literatur Bearbeiten
- 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.