Mengenüberdeckungsproblem
Das Mengenüberdeckungsproblem (oft auch Set Cover Problem) ist eine klassische Fragestellung in der Kombinatorik, der theoretischen Informatik und der kombinatorischen Optimierung. 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.
Problembeschreibung
Gegeben sei eine endliche Menge <math>U</math> und eine Menge <math>{\cal S}=\{S_1,\ldots,S_n\}</math>, die <math>n</math> Teilmengen <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 ganzzahliges lineares Optimierungsproblem 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
{{safesubst:#ifeq:0|10| {{#switch: Mengenüberdeckungsproblem |Navigationsleiste|NaviBlock|0=|#default= Vorlage:Templatetransclusioncheck Vorlage:Dokumentation/ruler }}}}Vorlage:Klappleiste/Anfang {{#if:
|
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
|
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 }} Vorlage:Klappleiste/Ende