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

Literatur

{{#invoke:Vorlage:Literatur|f}}

{{safesubst:#ifeq:0|10| {{#switch: Mengenpackungsproblem |Navigationsleiste|NaviBlock|0=|#default= Vorlage:Templatetransclusioncheck Vorlage:Dokumentation/ruler }}}}Vorlage:Klappleiste/Anfang {{#if:

|

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