Dato un universo U di n elementi, una raccolta di sottoinsiemi di U dice S = {S1, S2…,Sm} dove ogni sottoinsieme Si ha un costo associato. Trova una sottocollezione di costo minimo di S che copre tutti gli elementi di U.

Esempio:

Perché è utile?
E ‘ stato uno dei problemi NP-complete di Karp, dimostrato di essere così nel 1972. Altre applicazioni: copertura del bordo,copertura del vertice
Esempio interessante: IBM trova virus informatici (wikipedia)
Elementi – 5000 virus noti
Set – 9000 sottostringhe di 20 o più byte consecutivi da virus, non trovati nel codice ‘buono’.
È stato trovato un set di copertura di 180. È sufficiente cercare queste 180 sottostringhe per verificare l’esistenza di virus informatici noti.

Un altro esempio: Considera che General Motors deve acquistare una certa quantità di forniture varie e ci sono fornitori che offrono varie offerte per diverse combinazioni di materiali (Fornitore A: 2 tonnellate di acciaio + 500 piastrelle per x x; Fornitore B: 1 tonnellata di acciaio + 2000 piastrelle per y y; ecc.). È possibile utilizzare set cover per trovare il modo migliore per ottenere tutti i materiali riducendo al minimo i costi
Source: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Set Cover is NP-Hard:
Non esiste una soluzione temporale polinomiale disponibile per questo problema in quanto il problema è un noto problema NP-Hard. Esiste un algoritmo approssimativo avido di tempo polinomiale, l’algoritmo avido fornisce un algoritmo approssimativo Logn.

Esempio:
Consideriamo l’esempio precedente per capire l’algoritmo Greedy.

Prima iterazione:
I = {}

Il costo per nuovo elemento per S1 = Cost(S1)/|S1 – I| = 5/3

Il costo per nuovo elemento per S2 = Cost(S2)/|S2 – I| = 10/2

Il costo per nuovo elemento per S3 = Cost(S3)/|S3 – I| = 3/4

Poiché S3 ha valore minimo S3 viene aggiunto, I diventa {1,4,3,2}.

Seconda iterazione:
I = {1,4,3,2}

Il costo per nuovo elemento per S1 = Cost(S1)/|S1 – I| = 5/0
Nota che S1 non aggiunge alcun nuovo elemento a I.

Il costo per nuovo elemento per S2 = Cost(S2)/|S2 – I| = 10/1
Nota che S2 aggiunge solo 5 a I.

L’algoritmo greedy fornisce la soluzione ottimale per l’esempio precedente, ma potrebbe non fornire sempre una soluzione ottimale. Si consideri il seguente esempio.

Prova che l’algoritmo avido sopra è Logn approssimativo.
Lascia che OPT sia il costo della soluzione ottimale. Diciamo che gli elementi (k-1) sono coperti prima di un’iterazione dell’algoritmo avido sopra. Il costo dell’elemento k’th i che non è stato coperto prima del passaggio corrente dell’algoritmo greedy ed è lì in OPT. Poiché l’algoritmo greedy sceglie il Si più conveniente, il costo per elemento nel set selezionato deve essere inferiore a OPT diviso per gli elementi rimanenti. Pertanto costo dell’elemento k’th Costo dell’algoritmo Greedy = Somma dei costi di n elementi

Fonte: