givet et univers U af N elementer, en samling af delmængder af U sige S = {S1, S2…,Sm} hvor hver delmængde Si har en tilknyttet pris. Find en minimumspris subcollection af S, der dækker alle elementer i U.

eksempel:

hvorfor er det nyttigt?
Det var et af Karps NP-komplette problemer, der viste sig at være det i 1972. Andre applikationer: kant dækker, toppunkt cover
interessant eksempel: IBM finder computervirus
elementer – 5000 kendte vira
Sæt – 9000 understrenge på 20 eller flere på hinanden følgende byte fra vira, ikke fundet i ‘god’ kode.
Et sæt cover på 180 blev fundet. Det er tilstrækkeligt at søge efter disse 180 understrenge for at verificere eksistensen af kendte computervirus.

et andet eksempel: overvej, at General Motors skal købe en vis mængde forskellige forsyninger, og der er leverandører, der tilbyder forskellige tilbud til forskellige kombinationer af materialer (leverandør a: 2 tons stål + 500 fliser til$*; leverandør B: 1 ton stål + 2000 fliser til $y; etc.). Du kan bruge sætdækning til at finde den bedste måde at få alle materialerne på, mens du minimerer omkostningerne
kilde: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Set Cover er NP-Hard:
der er ingen polynomisk tidsløsning tilgængelig for dette problem, da problemet er et kendt NP-hårdt problem. Der er en polynomisk tid grådige omtrentlige algoritme, den grådige algoritme giver en logn omtrentlige algoritme.

eksempel:
Lad os overveje ovenstående eksempel for at forstå grådige algoritme.

første Iteration:
I = {}

prisen pr.nyt element for S1 = omkostninger(S1)/|S1 – i| = 5/3

prisen pr. nyt element for S2 = omkostninger(S2)/|S2 – I| = 10/2

prisen pr. nyt element for S3 = omkostninger(S3)/|S3 – I| = 3/4

da S3 har minimumsværdi S3 tilføjes, bliver jeg {1,4,3,2}.

anden Iteration:
I = {1,4,3,2}

omkostningerne pr. nyt element for S1 = omkostninger (S1)|/S1 – i/ = 5/0
Bemærk, at S1 ikke tilføjer noget nyt element til I.

omkostningerne pr. nyt element for S2 = omkostninger(S2)| / S2 – i / = 10/1
Bemærk, at S2 kun tilføjer 5 til I.

den grådige algoritme giver den optimale løsning til ovenstående eksempel, men det giver muligvis ikke optimal løsning hele tiden. Overvej følgende eksempel.

bevis for, at ovenstående grådige algoritme er Logn omtrentlig.
Lad OPT være omkostningerne ved optimal løsning. Sig (k-1) elementer er dækket før en iteration af ovenstående grådige algoritme. Omkostningerne ved det k ‘ th element i, der ikke er dækket før det nuværende trin med grådig algoritme, og det er der i OPT. Da greedy algoritme vælger den mest omkostningseffektive Si, per-element-omkostninger i det valgte sæt skal være mindre end OPT divideret med de resterende elementer. Derfor koster k ‘ th element omkostninger ved grådige algoritme = summen af omkostningerne ved n elementer

kilde: