Abdeckungsprobleme

Abdeckungsprobleme bezeichnet eine Klasse von Optimierungsproblemen, bei denen es darum geht, eine gegebene Grundmenge U durch die Wahl einer Teilmenge von Teilmengen S abzudecken. Ziel ist meist die Minimierung der Anzahl der gewählten Teilmengen oder deren Gesamtkosten, sodass jedes Element von U von zumindest einer ausgewählten Teilmenge enthalten ist.

Die bekannteste Form ist das Set Cover Problem (SCP). Hier liegt U = {elem1,..., elemn}, S = {S1,...,Sm} mit Si ⊆ U; die Aufgabe ist, eine minimale Untermenge von S zu finden, deren Vereinigung U ergibt. Das Gegenteil/duale Problem heißt Hitting Set. Weitere verwandte Probleme sind Vertex Cover (in Graphen: Knotenmenge, die alle Kanten berührt) und Dominating Set.

Komplexität: Abdeckungsprobleme sind überwiegend NP-schwer; die Entscheidungsvariante, ob eine Abdeckung mit höchstens k Teilmengen existiert, ist NP-vollständig. Empirische Algorithmen wie der greedige Algorithmus liefern eine O(log n)-Annäherung (n = Größe von U). Inapproximierbarkeitsergebnisse zeigen, dass bessere Allokationen in allgemeinem Fall schwer zu erreichen sind, es sei denn P=NP. Für bestimmte restriktive Instanzen oder Set-Systeme können verbesserte Approximationen oder sogar exakte Verfahren verfügbar sein.

Anwendungen: Ressourcenplanung, Netzdesign, Sensorplatzierung, Testkonstruktion, Datenkompression, Informationsretrieval und Logistik.