Establecer problema de portada

El problema de cobertura de conjuntos es una pregunta clásica en combinatoria , ciencias de la computación , investigación de operaciones y teoría de la complejidad . Es uno de los 21 problemas NP-completos de Karp que se mostró como NP-completo en 1972.

Se trata de un problema “cuyo estudio ha llevado al desarrollo de técnicas fundamentales para todo el campo” de los algoritmos de aproximación . ^[1]

Dado un conjunto de elementos (llamado el universo ) y una colección de conjuntos cuya unión es igual al universo, el problema de cobertura de conjuntos es identificar la subcolección más pequeña de cuya unión es igual al universo. Por ejemplo, considere el universo y la colección de conjuntos . Claramente la unión de es . Sin embargo, podemos cubrir todos los elementos con el siguiente número más pequeño de conjuntos: .${\ estilo de visualización \ {1,2,...,n\}}$${\ estilo de visualización S}$${\ estilo de visualización m}$${\ estilo de visualización S}$${\displaystyle U=\{1,2,3,4,5\}}$${\displaystyle S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}}$${\ estilo de visualización S}$${\ estilo de visualización U}$${\displaystyle \{\{1,2,3\},\{4,5\}\}}$

Más formalmente, dado un universo y una familia de subconjuntos de , una cubierta es una subfamilia de conjuntos cuya unión es . En el problema de decisión de cobertura de conjuntos , la entrada es un par y un número entero ; la pregunta es si hay un conjunto que cubre de tamaño o menos. En el problema de optimización de cobertura de conjuntos , la entrada es un par , y la tarea es encontrar una cobertura de conjuntos que use la menor cantidad de conjuntos.${\displaystyle {\mathcal {U}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {U}}}$${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$${\displaystyle {\mathcal {U}}}$${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$${\ estilo de visualización k}$${\ estilo de visualización k}$${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$

La versión de decisión de set cover es NP-complete , y la versión de optimización/búsqueda de set cover es NP-hard . ^[2]

Ejemplo ajustado para el algoritmo codicioso con k=3