Given a universe U of N elements, a collection of subsets of U say S = {S1, S2…,Sm} where every subset Si has an associated cost. Encontre uma subcolecção de custos mínimos de S que abranja todos os elementos de U.

exemplo:

Por que é útil?foi um dos problemas NP-completos De Karp, mostrado para ser assim em 1972. Outras aplicações: cobertura de aresta,cobertura de vértices exemplo interessante: IBM finds computer viruses(wikipedia)
Elements – 5000 known viruses
Sets – 9000 substrings of 20 or more consecutive bytes from viruses, not found in ‘good’ code.
Uma capa de conjunto de 180 foi encontrada. Basta procurar estes 180 substratos para verificar a existência de vírus de computador conhecidos.

Outro exemplo: Considere a General Motors precisa comprar uma certa quantidade de variadas suprimentos e há fornecedores que oferecem diversas ofertas para diferentes combinações de materiais (Fornecedor: 2 toneladas de aço + 500 telhas para $x; Fornecedor B: 1 tonelada de aço + 2000 telhas por us $y; etc.). Você pode usar o conjunto de cobertura para encontrar a melhor maneira de obter todos os materiais, minimizando o custo
Fonte: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Conjunto de Tampa é NP-Difícil:
não Há tempo polinomial solução para este problema, como o problema é um conhecido NP-Difícil problema. Há um algoritmo aproximado ganancioso em tempo polinomial, o algoritmo ganancioso fornece um algoritmo aproximado Logn.

exemplo:
vamos considerar o exemplo acima para entender algoritmo ganancioso.primeira iteração:
I = {}

por cada novo elemento de custo para S1 = Custo(S1)/|S1 – I| = 5/3

por cada novo elemento de custo para o S2 = Custo(S2)/|S2 – I| = 10/2

por cada novo elemento de custo para o S3 = Custo(S3)/|S3 – I| = 3/4

Desde o S3 tem valor mínimo S3 é adicionado, o eu torna-se {1,4,3,2}.

Segunda Iteração:
I = {1,4,3,2}

por cada novo elemento de custo para S1 = Custo(S1)/|S1 – I| = 5/0
Note que S1 não adicionar qualquer novo elemento para i

por cada novo elemento de custo para o S2 = Custo(S2)/|S2 – I| = 10/1
Note que S2 adiciona apenas a 5 / I.

o algoritmo ganancioso fornece a solução ideal para o exemplo acima, mas pode não fornecer a solução ideal o tempo todo. Considere o seguinte exemplo.

Proof that the above greedy algorithm is Logn approximate.
Let OPT be the cost of optimal solution. Say (k-1) elements are covered before an iteration of above greedy algorithm. O custo do elemento k’éth i que não foi coberto antes da etapa atual do algoritmo ganancioso e está lá em OPT. Uma vez que o algoritmo ganancioso escolhe o Si mais rentável, o custo por elemento no conjunto escolhido deve ser menor do que o OPT dividido pelos elementos restantes. Portanto, custo do elemento k’ésimo custo do algoritmo ganancioso = soma dos custos dos elementos n

fonte: