Dado un universo U de n elementos, una colección de subconjuntos de U, por ejemplo,S = {S1, S2 Sm, Sm} donde cada subconjunto Si tiene un costo asociado. Encuentre una subcolección de costo mínimo de S que cubra todos los elementos de U.

Ejemplo:

¿Por qué es útil?Fue uno de los problemas NP-complete de Karp, demostrado en 1972. Otras aplicaciones: cubierta de bordes, cubierta de vértices
Ejemplo interesante: IBM encuentra virus informáticos (wikipedia) Elementos – 5000 conjuntos de virus conocidos – 9000 subcadenas de 20 o más bytes consecutivos de virus, que no se encuentran en el código «bueno».
Se encontró una cubierta de juego de 180. Basta con buscar estas 180 subcadenas para verificar la existencia de virus informáticos conocidos.

Otro ejemplo: Considere que General Motors necesita comprar una cierta cantidad de suministros variados y hay proveedores que ofrecen varias ofertas para diferentes combinaciones de materiales (Proveedor A: 2 toneladas de acero + 500 baldosas por $x; Proveedor B: 1 tonelada de acero + 2000 baldosas por $y; etc.). Puede usar la cubierta del conjunto para encontrar la mejor manera de obtener todos los materiales al tiempo que minimiza el costo
Fuente: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

La cubierta del conjunto es NP-Duro:
No hay una solución de tiempo polinómico disponible para este problema, ya que el problema es un problema NP-Duro conocido. Hay un algoritmo aproximado codicioso de tiempo polinómico, el algoritmo codicioso proporciona un algoritmo aproximado de Logn.

Ejemplo:
consideremos el ejemplo anterior, para entender el Algoritmo Voraz.

Primera iteración:
I = {}

El costo por elemento nuevo para S1 = Costo(S1)/|S1 – I| = 5/3

El costo por elemento nuevo para S2 = Costo(S2)/|S2 – I| = 10/2

El costo por elemento nuevo para S3 = Costo(S3)/|S3 – I| = 3/4

Dado que S3 tiene un valor mínimo, se agrega S3, se 1,4,3,2}.

Segunda iteración:
I = {1,4,3,2}

El costo por elemento nuevo para S1 = Costo (S1)|/S1 – I/ = 5/0
Tenga en cuenta que S1 no agrega ningún elemento nuevo a I.

El costo por elemento nuevo para S2 = Costo(S2)| / S2 – I / = 10/1
Tenga en cuenta que S2 agrega solo 5 a I.

El algoritmo greedy proporciona la solución óptima para el ejemplo anterior, pero puede que no proporcione una solución óptima todo el tiempo. Considere el siguiente ejemplo.

Prueba de que el algoritmo codicioso anterior es aproximado al Logn.Deje que OPT sea el costo de la solución óptima. Digamos que los elementos (k-1) están cubiertos antes de una iteración del algoritmo codicioso anterior. El costo del elemento k’ésimo i que no ha sido cubierto antes del paso actual del algoritmo codicioso y está allí en OPT. Dado que el algoritmo codicioso elige el Si más rentable, el costo por elemento en el conjunto seleccionado debe ser menor que el OPT dividido por los elementos restantes. Por lo tanto, costo del elemento k’ésimo Costo del Algoritmo Codicioso = Suma de costos de n elementos

Fuente: