Mengenpackungsproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 \le 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[Bearbeiten]

Literatur[Bearbeiten]

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