Mengenüberdeckungsproblem

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

• Mengenpackungsproblem
• Mengenzerlegungsproblem

Karps 21 NP-vollständige Probleme

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