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\leq 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

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

Karps 21 NP-vollständige Probleme

Erfüllbarkeitsproblem der Aussagenlogik | Cliquenproblem | Mengenpackungsproblem | Knotenüberdeckungsproblem | Mengenüberdeckungsproblem | Feedback Arc Set | Feedback Vertex Set | Hamiltonkreisproblem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by cliques | Problem der exakten Überdeckung | 3-dimensional matching | Steinerbaumproblem | Hitting set | Rucksackproblem | Job sequencing | Partitionsproblem | Maximaler Schnitt