Mengenpackungsproblem

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

Es fragt, ob zu einer endlichen Menge <math>U</math> und <math>n</math> Teilmengen <math>S_j</math> von <math>U</math> eine Anzahl von mindestens <math>k \le n</math> paarweise disjunkter Teilmengen <math>S_j</math> existieren.

Als Optimierungsproblem formuliert, wird eine Packung mit möglichst vielen Teilmengen <math>S_j</math> gesucht oder, falls den Teilmengen <math>S_j</math> Bewertungen <math>c_j</math> 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. 

Vorlage:Klappleiste/Anfang 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 Vorlage:Klappleiste/Ende