Set Cover (auch Mengenüberdeckung) ist ein klassisches NP-schweres Optimierungsproblem: Gegeben sind eine Grundmenge U und eine Familie von Teilmengen. Gesucht ist die kleinste Teilfamilie, deren Vereinigung die gesamte Grundmenge U ergibt — jede Auswahl von Teilmengen muss also jedes Element mindestens einmal „abdecken“.
Problemdefinition
Gegben: eine endliche Grundmenge U (etwa alle zu testenden Funktionen) und eine Sammlung von Teilmengen S1, S2, …, Sm, deren Vereinigung U ist. Gesucht: eine minimale Teilmenge der Indizes, sodass die zugehörigen Mengen zusammen jedes Element von U enthalten. In der Entscheidungsvariante „gibt es eine Überdeckung mit höchstens k Mengen?“ ist Set Cover NP-vollständig (eines der 21 Karp-Probleme von 1972).
Der Greedy-Algorithmus
Die bekannteste Heuristik ist gierig: Wähle in jedem Schritt die Teilmenge, die die meisten noch nicht abgedeckten Elemente neu abdeckt, bis alles abgedeckt ist. Der Greedy-Algorithmus erreicht garantiert eine Lösung, die höchstens um den Faktor ln(n) schlechter ist als das Optimum (n = Anzahl der Elemente). Unter der Annahme P ≠ NP gibt es keinen Polynomialzeitalgorithmus mit Approximationsfaktor besser als c·ln(n). Der Greedy-Algorithmus ist hier also nahe am theoretisch Machbaren.
Anwendungen
- Standortplanung: minimale Menge an Standorten, sodass alle Kunden abgedeckt sind
- Crew- und Schichtplanung: minimale Crews, die alle Flüge bedienen
- Testabdeckung: minimale Testfälle, die alle Code-Zweige erreichen
- Maximal-Abdeckungs-Problem als Variante mit Budget
Verwandte Probleme
Set Cover ist die allgemeine Form vieler Überdeckungsprobleme. Wichtige Spezialfälle sind die Knotenüberdeckung (Vertex Cover) und das Hitting-Set-Problem. Gemeinsam mit Satisfiability (SAT) gehört es zur Klasse der NP-vollständigen Probleme; für viele Praxisinstanzen liefern Approximationsalgorithmen gute Lösungen.