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 und Teilmengen von und einer natürlichen Zahl eine Vereinigung von oder weniger Teilmengen existiert, die der Menge entspricht (Überdeckung).

Als Optimierungsproblem formuliert, wird eine Überdeckung mit möglichst kleiner Anzahl der Teilmengen gesucht oder, falls den Teilmengen Kosten 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 | Quelltext bearbeiten]