givet ett universum U av n-element, säger en samling delmängder av U S = {S1, S2…,Sm} där varje delmängd Si har en tillhörande kostnad. Hitta en minimikostnadsundersamling av S som täcker alla delar av U.

exempel:

Varför är det användbart?
det var ett av Karps NP-fullständiga problem, visat sig vara så 1972. Andra tillämpningar:kant täcker, vertex täcka
intressant exempel: IBM hittar datavirus(wikipedia)
Elements – 5000 kända virus
Sets – 9000 substrings av 20 eller fler på varandra följande byte från virus, som inte finns i ’bra’ kod.
en uppsättning omslag på 180 hittades. Det räcker att söka efter dessa 180 delsträngar för att verifiera förekomsten av kända datavirus.

ett annat exempel: överväga General Motors behöver köpa en viss mängd olika leveranser och det finns leverantörer som erbjuder olika erbjudanden för olika kombinationer av material (leverantör A: 2 ton stål + 500 plattor för $x; leverantör B: 1 ton stål + 2000 plattor för $y; etc.). Du kan använda set covering för att hitta det bästa sättet att få allt material samtidigt minimera kostnaden
Källa: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Set Cover är NP-Hard:
det finns ingen polynom tidslösning tillgänglig för detta problem eftersom problemet är ett känt NP-Hard problem. Det finns en polynom tid girig ungefärlig algoritm, den giriga algoritmen ger en logn ungefärlig algoritm.

exempel:
låt oss betrakta ovanstående exempel för att förstå giriga algoritm.

första iterationen:
i = {}

kostnaden per nytt element för S1 = kostnad(S1)/|S1 – I| = 5/3

kostnaden per nytt element för S2 = kostnad(S2)/|S2 – I| = 10/2

kostnaden per nytt element för S3 = kostnad(S3)/|S3 – i| = 3/4

eftersom S3 har minimivärde S3 läggs till blir jag {1,4,3,2}.

andra Iteration:
i = {1,4,3,2}

kostnaden per nytt element för S1 = kostnad(S1)/|S1 – I| = 5/0
Observera att S1 inte lägger till något nytt element i I.

kostnaden per nytt element för S2 = kostnad(S2)/|S2 – i| = 10/1
Observera att S2 bara lägger till 5 till I.

den giriga algoritmen ger den optimala lösningen för ovanstående exempel, men det kanske inte ger optimal lösning hela tiden. Tänk på följande exempel.

bevis på att ovanstående giriga algoritm är logn ungefärlig.
låt OPT vara kostnaden för optimal lösning. Säg (k-1) element täcks före en iteration av ovanstående giriga algoritm. Kostnaden för K ’ TH-elementet jag som inte har täckts före det aktuella steget med girig algoritm och det finns där i OPT. Eftersom girig algoritm plockar den mest kostnadseffektiva Si, per-element-kostnad i plockade set måste vara mindre än OPT dividerat med återstående element. Därför kostnaden för K ’ TH element kostnaden för girig algoritm = summan av kostnaderna för n element

källa: