~2026-10978-01: /* Problembeschreibung */ Notation korrigiert

2026-02-18T17:17:09Z

Problembeschreibung: Notation korrigiert

Neue Seite

[[Datei:SetCover.svg|mini|Eine Instanz des Mengenüberdeckungsproblems]]
Das '''Mengenüberdeckungsproblem''' (oft auch ''Set Cover Problem'') ist eine klassische Fragestellung in der [[Kombinatorik]], der [[Theoretische Informatik|theoretischen Informatik]] und der [[Kombinatorische Optimierung|kombinatorischen Optimierung]]. Das Mengenüberdeckungsproblem gehört zur Liste der [[Karps 21 NP-vollständige Probleme|21 klassischen NP-vollständigen Probleme]], von denen [[Richard M. Karp|Richard Karp]] [[1972]] die Zugehörigkeit zu dieser Klasse zeigen konnte.

== Problembeschreibung ==
Gegeben sei eine endliche [[Menge (Mathematik)|Menge]] <math>U</math> und eine Menge <math>{\cal S}=\{S_1,\ldots,S_n\}</math>, die <math>n</math> [[Teilmenge]]n <math>S_i</math> von <math>U</math> enthält. Gesucht ist nun eine möglichst kleine Teilmenge <math>{\cal X} \subseteq {\cal S}</math>, deren Elemente die Menge <math>U</math> überdecken.

In folgendem Beispiel, welches nebenstehend abgebildet ist, sind <math>U=\{1,\ldots,5\}</math> und <math>{\cal S}=\{\{1, 2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 5\}\}</math>. Die Vereinigung aller Mengen aus <math>\cal S</math> ist offensichtlich die Menge <math>U</math>. Allerdings können alle Elemente aus <math>U</math> auch mit den Teilmengen <math>\{1, 2, 3\}</math> und <math>\{4, 5\}</math> dargestellt werden, welche eine Lösung des Set Cover Problems in diesem Beispiel darstellen.

== Das gewichtete Mengenüberdeckungsproblem ==
Im gewichteten Mengenüberdeckungsproblem (''Minimum Weight Set Cover Problem'') werden jeder Teilmenge <math>S_i\in\cal S</math> außerdem Kosten <math>c_i\in\mathbb R</math> zugewiesen und es gilt eine kostenminimale Überdeckung der Menge <math>U</math> zu bestimmen. Für <math>c_i=1</math> entspricht dies dem klassischen Set Cover Problem.

== Formulierung als Optimierungsproblem ==
Das gewichtete Mengenüberdeckungsproblem kann als [[Ganzzahlige lineare Optimierung|ganzzahliges lineares Optimierungsproblem]] [[Optimierungsmodell|modelliert]] werden. Dazu sei <math>y_i\in\{0,1\}</math> eine binäre [[Entscheidungsvariable]], die angibt, ob die Teilmenge <math>S_i</math> Teil der optimalen Auswahl <math>X</math> ist (<math>y_i=1</math>) oder nicht (<math>y_i=0</math>). Die zu minimierende [[Zielfunktion]] ist die gewichtete Summe aller ausgewählten Teilmengen <math display="inline">\sum_{i=1}^nc_iy_i</math> und die Nebenbedingungen <math>\sum_{i:v\in S_i}y_i\ge 1\ \forall u\in U</math> garantieren, dass jedes Element <math>u\in U</math> in mindestens einer ausgewählten Menge <math>S_i</math> enthalten ist.

== Literatur ==
*Egon Balas, Manfred W. Padberg: ''On the Set-Covering Problem''. Operations Research, Vol. 20, Nr. 6, 1972

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

{{SORTIERUNG:Mengenuberdeckungsproblem}}
[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Kombinatorische Optimierung]]

Mengenüberdeckungsproblem - Versionsgeschichte

~2026-10978-01: /* Problembeschreibung */ Notation korrigiert