Establecer problema de portada - Set cover problem

El problema de cobertura de conjuntos es una cuestión clásica en combinatoria , informática , investigación de operaciones y teoría de la complejidad . Es uno de los 21 problemas NP-completo de Karp que se demostró que era 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 .

Dado un conjunto de elementos (llamado universo ) y una colección de conjuntos cuya unión es igual al universo, el problema de cobertura del conjunto es identificar la sub-colecció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 la totalidad de los elementos con el siguiente, menor número de conjuntos: . ${\ Displaystyle \ {1,2, ..., n \}}$ ${\ Displaystyle S}$ ${\ Displaystyle m}$ ${\ Displaystyle S}$ ${\ Displaystyle U = \ {1,2,3,4,5 \}}$ ${\ Displaystyle S = \ {\ {1,2,3 \}, \ {2,4 \}, \ {3,4 \}, \ {4,5 \} \}}$ ${\ Displaystyle S}$ ${\ Displaystyle 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 que cubre el conjunto , la entrada es un par y un número entero ; la pregunta es si existe una cobertura de conjunto de tamaño o menor. 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 utilice 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}})}$ ${\ Displaystyle k}$ ${\ Displaystyle k}$ ${\ Displaystyle ({\ mathcal {U}}, {\ mathcal {S}})}$

La versión de decisión de la cobertura del conjunto es NP-complete , y la versión de optimización / búsqueda de la cobertura del conjunto es NP-hard .

Si a cada conjunto se le asigna un costo, se convierte en un problema de cobertura de conjunto ponderado .

Formulación de programas lineales enteros

El problema de cobertura del conjunto mínimo se puede formular como el siguiente programa lineal de enteros (ILP).

minimizar	${\ Displaystyle \ sum _ {s \ in {\ mathcal {S}}} x_ {s}}$		(minimizar el número de juegos)
sujeto a	${\ Displaystyle \ sum _ {s \ colon e \ in s} x_ {s} \ geqslant 1}$	para todos ${\ Displaystyle e \ in {\ mathcal {U}}}$	(cubre todos los elementos del universo)
	${\ Displaystyle x_ {s} \ in \ {0,1 \}}$	para todos . ${\ Displaystyle s \ in {\ mathcal {S}}}$	(cada juego está en la portada del juego o no)

Este ILP pertenece a la clase más general de ILP para cubrir problemas . La brecha de integralidad de este ILP es como máximo , por lo que su relajación proporciona un algoritmo de aproximación de factores para el problema de cobertura del conjunto mínimo (donde está el tamaño del universo). ${\ Displaystyle \ scriptstyle \ log n}$ ${\ Displaystyle \ scriptstyle \ log n}$ ${\ Displaystyle \ scriptstyle n}$

En la cubierta de conjuntos ponderados, a los conjuntos se les asignan pesos. Denote el peso del conjunto por . Entonces, el programa lineal de enteros que describe la cobertura del conjunto ponderado es idéntico al dado anteriormente, excepto que la función objetivo para minimizar es . ${\ Displaystyle s \ in {\ mathcal {S}}}$ ${\ Displaystyle w_ {s}}$ ${\ Displaystyle \ sum _ {s \ in {\ mathcal {S}}} w_ {s} x_ {s}}$

Formulación de conjunto de golpes

La cobertura del set es equivalente al problema del set de golpes . Eso se ve al observar que una instancia de cobertura de conjunto puede verse como un gráfico bipartito arbitrario , con conjuntos representados por vértices a la izquierda, el universo representado por vértices a la derecha y aristas que representan la inclusión de elementos en conjuntos. La tarea es entonces encontrar un subconjunto de cardinalidad mínima de vértices izquierdos que cubra todos los vértices derechos. En el problema del conjunto de golpes, el objetivo es cubrir los vértices izquierdos utilizando un subconjunto mínimo de los vértices derechos. Por lo tanto, la conversión de un problema a otro se logra intercambiando los dos conjuntos de vértices.

Algoritmo codicioso

Existe un algoritmo codicioso para la aproximación de tiempo polinomial de la cobertura de conjuntos que elige conjuntos de acuerdo con una regla: en cada etapa, elija el conjunto que contiene la mayor cantidad de elementos descubiertos. Este método se puede implementar en tiempo lineal en la suma de tamaños de los conjuntos de entrada, utilizando una cola de depósito para priorizar los conjuntos. Alcanza una relación de aproximación de , donde es el tamaño del conjunto a cubrir. En otras palabras, encuentra una cobertura que puede ser veces tan grande como la mínima, donde está el -ésimo número armónico : ${\ Displaystyle H (s)}$ ${\ Displaystyle s}$ ${\ Displaystyle H (n)}$ ${\ Displaystyle H (n)}$ ${\ Displaystyle n}$

{\ Displaystyle H (n) = \ sum _ {k = 1} ^ {n} {\ frac {1} {k}} \ leq \ ln {n} +1}

Este algoritmo codicioso en realidad logra una relación de aproximación de dónde está el conjunto de cardinalidad máxima de . Para instancias densas, sin embargo, existe un algoritmo de aproximación para cada . ${\ Displaystyle H (s ^ {\ prime})}$ ${\ Displaystyle s ^ {\ prime}}$ ${\ Displaystyle S}$ ${\ Displaystyle \ delta -}$ ${\ Displaystyle c \ ln {m}}$ ${\ Displaystyle c> 0}$

Estrecho ejemplo para el algoritmo codicioso con k = 3

Hay un ejemplo estándar en el que el algoritmo codicioso logra una relación de aproximación de . El universo consta de elementos. El sistema de conjuntos consta de conjuntos disjuntos por pares con tamaños respectivamente, así como dos conjuntos disjuntos adicionales , cada uno de los cuales contiene la mitad de los elementos de cada uno . En esta entrada, el algoritmo codicioso toma los conjuntos , en ese orden, mientras que la solución óptima consiste solo en y . A la derecha se muestra un ejemplo de una entrada de este tipo. ${\ Displaystyle \ log _ {2} (n) / 2}$ ${\ Displaystyle n = 2 ^ {(k + 1)} - 2}$ ${\ Displaystyle k}$ ${\ Displaystyle S_ {1}, \ ldots, S_ {k}}$ ${\ Displaystyle 2,4,8, \ ldots, 2 ^ {k}}$ ${\ Displaystyle T_ {0}, T_ {1}}$ ${\ Displaystyle S_ {i}}$ ${\ Displaystyle S_ {k}, \ ldots, S_ {1}}$ ${\ Displaystyle T_ {0}}$ ${\ Displaystyle T_ {1}}$ ${\ Displaystyle k = 3}$

Los resultados de inaproximación muestran que el algoritmo codicioso es esencialmente el mejor algoritmo de aproximación de tiempo polinomial posible para la cobertura de conjuntos hasta términos de orden inferior (consulte los resultados de inaproximación a continuación), bajo supuestos de complejidad plausibles. Un análisis más estricto del algoritmo codicioso muestra que la relación de aproximación es exactamente . ${\ Displaystyle \ ln {n} - \ ln {\ ln {n}} + \ Theta (1)}$

Sistemas de baja frecuencia

Si cada elemento ocurre en un máximo de conjuntos f , entonces se puede encontrar una solución en el tiempo polinomial que se aproxime al óptimo dentro de un factor de f usando relajación LP .

Si la restricción se sustituye por para todos S en en el número entero lineal programa mostrado anteriormente , entonces se convierte en un (no entero) lineal programa L . El algoritmo se puede describir de la siguiente manera: ${\ Displaystyle x_ {S} \ in \ {0,1 \}}$ ${\ Displaystyle x_ {S} \ geq 0}$ ${\ Displaystyle {\ mathcal {S}}}$

Encuentre una solución óptima O para el programa L usando algún método de tiempo polinomial para resolver programas lineales.
Recoger todos los conjuntos S para el que la variable correspondiente x _S tiene un valor de al menos 1 / f en la solución de O .

Resultados de inapropiabilidad

Cuando se refiere al tamaño del universo, Lund y Yannakakis (1994) mostraron que la cobertura de conjuntos no puede aproximarse en tiempo polinomial dentro de un factor de , a menos que NP tenga algoritmos de tiempo cuasi-polinomial . Feige (1998) mejoró este límite inferior bajo los mismos supuestos, que esencialmente coincide con la relación de aproximación lograda por el algoritmo codicioso. Raz y Safra (1997) establecieron un límite inferior de , donde es una cierta constante, bajo el supuesto más débil de que P NP . Recientemente , Alon, Moshkovitz & Safra (2006) demostraron un resultado similar con un valor más alto de . Dinur y Steurer (2013) mostraron una inaproximación óptima al demostrar que no se puede aproximar a menos que P NP . ${\ Displaystyle n}$ ${\ Displaystyle {\ tfrac {1} {2}} \ log _ {2} {n} \ aproximadamente 0,72 \ ln {n}}$ ${\ Displaystyle {\ bigl (} 1-o (1) {\ bigr)} \ cdot \ ln {n}}$ ${\ Displaystyle c \ cdot \ ln {n}}$ ${\ Displaystyle c}$ ${\ Displaystyle \ not =}$ ${\ Displaystyle c}$ ${\ Displaystyle {\ bigl (} 1-o (1) {\ bigr)} \ cdot \ ln {n}}$ ${\ displaystyle =}$

Funda de juego ponderada

Al relajar el programa lineal de enteros para la cobertura del conjunto ponderado indicado anteriormente , se puede usar el redondeo aleatorio para obtener una aproximación de factores. El análisis correspondiente para la cobertura del conjunto no ponderado se describe en Redondeo aleatorio # Algoritmo de redondeo aleatorio para la cobertura del conjunto y se puede adaptar al caso ponderado. ${\ Displaystyle O (\ log n)}$

Problemas relacionados

Golpear el set es una reformulación equivalente de Set Cover.
La cubierta de vértice es un caso especial de Hitting Set.
La funda Edge es un caso especial de Set Cover.
La cobertura de conjuntos geométricos es un caso especial de cobertura de conjuntos cuando el universo es un conjunto de puntos y los conjuntos son inducidos por la intersección del universo y las formas geométricas (por ejemplo, discos, rectángulos). ${\ Displaystyle \ mathbb {R} ^ {d}}$
Establecer embalaje
El problema de cobertura máxima es elegir como máximo k conjuntos para cubrir tantos elementos como sea posible.
El conjunto dominante es el problema de seleccionar un conjunto de vértices (el conjunto dominante) en un gráfico de modo que todos los demás vértices sean adyacentes a al menos un vértice en el conjunto dominante. Se demostró que el problema del set dominante es NP completo mediante una reducción de la cobertura del set.
El problema exacto de la cubierta es elegir una cubierta del juego sin ningún elemento incluido en más de un juego de cubierta.
Cubierta roja azul

Notas

Referencias

Alon, Noga ; Moshkovitz, Dana ; Safra, Shmuel (2006), "algorítmico construcción de conjuntos de k-restricciones", ACM Trans. Algoritmos , 2 (2): 153–177, CiteSeerX 10.1.1.138.8682 , doi : 10.1145 / 1150334.1150336 , ISSN 1549-6325 , S2CID 11922650.
Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), Introducción a los algoritmos , Cambridge, Mass .: MIT Press y McGraw-Hill, págs. 1033–1038, ISBN 978-0-262-03293-3
Feige, Uriel (1998), "Un umbral de ln n para aproximar la cobertura del conjunto", Journal of the ACM , 45 (4): 634–652, CiteSeerX 10.1.1.70.5014 , doi : 10.1145 / 285055.285059 , ISSN 0004-5411 , S2CID 52827488.
Karpinski, Marek; Zelikovsky, Alexander (1998), "Aproximación de casos densos de problemas de cobertura", Actas del taller DIMACS sobre diseño de redes: conectividad y ubicación de instalaciones , 40 , págs. 169-178, ISBN 9780821870846
Lund, Carsten ; Yannakakis, Mihalis (1994), "Sobre la dureza de la aproximación de problemas de minimización", Journal of the ACM , 41 (5): 960–981, doi : 10.1145 / 185675.306789 , ISSN 0004-5411 , S2CID 9021065.
Raz, Ran ; Safra, Shmuel (1997), "Una prueba sub-constante de probabilidad de error de bajo grado y una caracterización de PCP de probabilidad de error sub-constante de NP", STOC '97: Actas del vigésimo noveno simposio anual de ACM sobre teoría de informática , ACM, págs. 475–484, ISBN 978-0-89791-888-6.
Dinur, Irit ; Steurer, David (2013), "Enfoque analítico de la repetición paralela", STOC '14: Actas del cuadragésimo sexto simposio anual de ACM sobre teoría de la computación , ACM, págs. 624–633.
Vazirani, Vijay V. (2001), Algoritmos de aproximación (PDF) , Springer-Verlag, ISBN 978-3-540-65367-7
Korte, Bernhard ; Vygen, Jens (2012), Optimización combinatoria: teoría y algoritmos (5 ed.), Springer, ISBN 978-3-642-24487-2
Cardoso, Nuno; Abreu, Rui (2014), "An Efficient Distributed Algorithm for Computing Minimal Hitting Sets" (PDF) , Actas del 25º Taller internacional sobre principios de diagnóstico , Graz, Austria, doi : 10.5281 / zenodo.10037

Languages

In other projects