Mengenüberdeckungsproblem

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

Das Mengenüberdeckungsproblem (oft mit set-covering-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik.

Es fragt, ob zu einer Menge U und n Teilmengen S_j von U und einer natürlichen Zahl k \le n eine Vereinigung von k oder weniger Teilmengen S_j existiert, die der Menge U entspricht (Überdeckung).

Als Optimierungsproblem formuliert, wird eine Überdeckung mit möglichst kleiner Anzahl der Teilmengen S_j gesucht oder, falls den Teilmengen S_j Kosten c_j zugeordnet sind, eine Überdeckung mit geringsten Kosten.

Das Mengenüberdeckungsproblem gehört zur Liste der 21 klassischen NP-vollständigen Probleme von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.

Siehe auch[Bearbeiten]