- 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 Sj von U eine Anzahl von mindestens paarweise disjunkter Teilmengen Sj existieren.
Als Optimierungsproblem formuliert, wird eine Packung mit möglichst vielen Teilmengen Sj gesucht oder, falls den Teilmengen Sj Bewertungen cj 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
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.
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
Wikimedia Foundation.