imported>Tambora am 28. September 2019 um 19:47 Uhr

2019-09-28T19:47:16Z

Neue Seite

Das '''Mengenpackungsproblem''' (oft mit ''set-packing-Problem'' notiert) ist ein [[Entscheidbar|Entscheidungsproblem]] der [[Kombinatorik]].

Es fragt, ob zu einer [[Endliche Menge|endlichen Menge]] <math>U</math> und <math>n</math> [[Teilmenge]]n <math>S_j</math> von <math>U</math> eine Anzahl von mindestens <math>k \le n</math> paarweise [[disjunkt]]er 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 [[Karps 21 NP-vollständige Probleme|21 klassischen NP-vollständigen Probleme]], von denen [[Richard M. Karp]] 1972 die Zugehörigkeit zu dieser [[Komplexitätsklasse|Klasse]] zeigen konnte.

==Siehe auch==

* [[Mengenüberdeckungsproblem]]
* [[Mengenzerlegungsproblem]]

== Literatur ==
* {{Literatur| Autor = Michael R. Garey and David S. Johnson | Jahr = 1979 | Titel = Computers and Intractability. A Guide to the Theory of NP-Completeness | Verlag = W.H. Freeman | ISBN = 0-7167-1045-5 | Seiten=221 | Kapitel=A3.1 SP3}}

{{Navigationsleiste Karps 21 NP-vollständige Probleme}}

[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Kombinatorische Optimierung]]

Mengenpackungsproblem - Versionsgeschichte

imported>Tambora am 28. September 2019 um 19:47 Uhr