Problema con la cubierta del conjunto

Problema clásico en combinatoria

Ejemplo de una instancia de problema de cobertura de conjunto.

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 .

Dado un conjunto de elementos {1, 2, …, n } (en adelante denominado el universo , especificando todos los elementos posibles bajo consideración) y una colección, denominada S , de m subconjuntos dados cuya unión es igual al universo, el problema de cobertura de conjuntos es identificar una subcolección más pequeña de S cuya unión es igual al universo.

Por ejemplo, considere el universo, U = {1, 2, 3, 4, 5} y la colección de conjuntos S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }. En este ejemplo, m es igual a 4, ya que hay cuatro subconjuntos que componen esta colección. La unión de S es igual a U . Sin embargo, podemos cubrir todos los elementos con solo dos conjuntos: { {1, 2, 3}, {4, 5} } ‍ , vea la imagen, pero no con un solo conjunto. Por lo tanto, la solución al problema de cobertura de conjuntos para este U y S tiene tamaño 2.

Más formalmente, dado un universo y una familia de subconjuntos de , una cubierta de conjunto es una subfamilia de conjuntos cuya unión es . ${\displaystyle {\mathcal {U}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {U}}}$ ${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$ ${\displaystyle {\mathcal {U}}}$

• En el problema de decisión de cobertura de conjunto , la entrada es un par y un entero ; la pregunta es si existe una cobertura de conjunto de tamaño o menor. ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$ ${\displaystyle k}$ ${\displaystyle k}$
• 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}},{\mathcal {S}})}$

La versión de decisión del cubrimiento de conjuntos es NP-completo . Es uno de los 21 problemas NP-completos de Karp que se demostró que eran NP-completos en 1972. La versión de optimización/búsqueda del cubrimiento de conjuntos es NP-hard . ^[1] Es un problema "cuyo estudio ha llevado al desarrollo de técnicas fundamentales para todo el campo" de los algoritmos de aproximación . ^[2]

Variantes

En el problema de cobertura de conjuntos ponderados , a cada conjunto se le asigna un peso positivo (que representa su costo) y el objetivo es encontrar una cobertura de conjunto con el menor peso. La cobertura de conjunto habitual (no ponderada) corresponde a todos los conjuntos que tienen un peso de 1.

En el problema de cobertura de conjuntos fraccionarios , se permite seleccionar fracciones de conjuntos, en lugar de conjuntos enteros. Una cobertura de conjuntos fraccionarios es una asignación de una fracción (un número en [0,1]) a cada conjunto en , de modo que para cada elemento x en el universo, la suma de fracciones de conjuntos que contienen x sea al menos 1. El objetivo es encontrar una cobertura de conjuntos fraccionarios en la que la suma de fracciones sea lo más pequeña posible. Tenga en cuenta que una cobertura de conjuntos (usual) es equivalente a una cobertura de conjuntos fraccionarios en la que todas las fracciones son 0 o 1; por lo tanto, el tamaño de la cobertura fraccionaria más pequeña es como máximo el tamaño de la cobertura más pequeña, pero puede ser menor. Por ejemplo, considere el universo U = {1, 2, 3} y la colección de conjuntos S = { {1, 2}, {2, 3}, {3, 1} }. La cobertura de conjuntos más pequeña tiene un tamaño de 2, por ejemplo { {1, 2}, {2, 3} }. Pero existe una cobertura de conjunto fraccionario de tamaño 1,5, en la que se toma una fracción de 0,5 de cada conjunto. ${\displaystyle {\mathcal {S}}}$

Formulación de programa lineal

El problema de cobertura de conjuntos se puede formular como el siguiente programa lineal entero (ILP). ^[3]

Para una representación más compacta de la restricción de cobertura, se puede definir una matriz de incidencia , donde cada fila corresponde a un elemento y cada columna corresponde a un conjunto, y si el elemento e está en el conjunto s, y en caso contrario. Entonces, la restricción de cobertura se puede escribir como . ${\displaystyle A}$ ${\displaystyle A_{e,s}=1}$ ${\displaystyle A_{e,s}=0}$ ${\displaystyle Ax\geqslant 1}$

La cobertura del conjunto ponderado se describe mediante un programa idéntico al dado anteriormente, excepto que la función objetivo a minimizar es , donde es el peso del conjunto . ${\displaystyle \sum _{s\in {\mathcal {S}}}w_{s}x_{s}}$ ${\displaystyle w_{s}}$ ${\displaystyle s\in {\mathcal {S}}}$

La cobertura del conjunto fraccionario se describe mediante un programa idéntico al dado anteriormente, excepto que puede ser un número no entero, por lo que la última restricción se reemplaza por . ${\displaystyle x_{s}}$ ${\displaystyle 0\leq x_{s}\leq 1}$

Este programa lineal pertenece a la clase más general de LP para problemas de cobertura , ya que todos los coeficientes en la función objetivo y ambos lados de las restricciones son no negativos. La brecha de integralidad del ILP es como máximo (donde es el tamaño del universo). Se ha demostrado que su relajación de hecho da un algoritmo de aproximación factorial para el problema de cobertura del conjunto mínimo. ^[4] Consulte randomized rounding#setcover para una explicación detallada. ${\displaystyle \scriptstyle \log n}$ ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle \log n}$

Formulación del set de bateo

El cubrimiento de conjuntos es equivalente al problema de los conjuntos impactantes . Esto se ve al observar que una instancia de cubrimiento de conjuntos puede verse como un grafo bipartito arbitrario , con el universo representado por vértices a la izquierda, los conjuntos representados por vértices a la derecha y las aristas representando la pertenencia de elementos a conjuntos. La tarea es entonces encontrar un subconjunto de cardinalidad mínima de vértices izquierdos que tenga una intersección no trivial con cada uno de los vértices derechos, que es precisamente el problema de los conjuntos impactantes.

En el campo de la geometría computacional , un conjunto de impacto para una colección de objetos geométricos también se denomina conjunto de punción o conjunto de perforación . ^[5]

Algoritmo codicioso

Existe un algoritmo voraz para la aproximación en tiempo polinomial del cubrimiento de conjuntos que elige conjuntos según una regla: en cada etapa, elige el conjunto que contiene el mayor número 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 cubos para priorizar los conjuntos. ^[6] Logra una relación de aproximación de , donde es el tamaño del conjunto a cubrir. ^[7] En otras palabras, encuentra un cubrimiento que puede ser 10 veces más grande que el mínimo, donde es 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 voraz en realidad logra una relación de aproximación de donde es el conjunto de cardinalidad máxima de . Sin embargo, para instancias densas, existe un algoritmo de aproximación para cada . ^[8] ${\displaystyle H(s^{\prime })}$ ${\displaystyle s^{\prime }}$ ${\displaystyle S}$ ${\displaystyle \delta -}$ ${\displaystyle c\ln {m}}$ ${\displaystyle c>0}$

Ejemplo estricto del algoritmo voraz con k=3

Hay un ejemplo estándar en el que el algoritmo voraz logra una razó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 . En esta entrada, el algoritmo voraz toma los conjuntos , en ese orden, mientras que la solución óptima consta solo de y . Un ejemplo de una entrada de este tipo para se muestra a la derecha. ${\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 inaproximabilidad muestran que el algoritmo voraz es esencialmente el mejor algoritmo de aproximación de tiempo polinomial posible para la cobertura de conjuntos hasta términos de orden inferior (ver los resultados de inaproximabilidad a continuación), bajo supuestos de complejidad plausibles. Un análisis más estricto para el algoritmo voraz muestra que la razón de aproximación es exactamente . ^[9] ${\displaystyle \ln {n}-\ln {\ln {n}}+\Theta (1)}$

Sistemas de baja frecuencia

Si cada elemento aparece en como máximo f conjuntos, entonces se puede encontrar una solución en tiempo polinomial que se aproxima al óptimo dentro de un factor de f utilizando la relajación LP .

Si la restricción se reemplaza por para todo S en el programa lineal entero que se muestra arriba, entonces se convierte en un programa lineal (no entero) L . El algoritmo se puede describir de la siguiente manera: ${\displaystyle x_{S}\in \{0,1\}}$ ${\displaystyle x_{S}\geq 0}$ ${\displaystyle {\mathcal {S}}}$

1. Encuentre una solución óptima O para el programa L utilizando algún método de tiempo polinomial para resolver programas lineales.
2. Elija todos los conjuntos S para los cuales la variable correspondiente x _S tenga un valor al menos 1/ f en la solución O . ^[10]

Resultados de inaproximabilidad

Cuando se refiere al tamaño del universo, Lund y Yannakakis (1994) demostraron 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 a bajo los mismos supuestos, lo que esencialmente coincide con la relación de aproximación lograda por el algoritmo voraz. 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 . Un resultado similar con un valor más alto de fue demostrado recientemente por Alon, Moshkovitz y Safra (2006). Dinur y Steurer (2013) demostraron una inaproximabilidad óptima al demostrar que no puede aproximarse a a menos que P NP . ${\displaystyle n}$ ${\displaystyle {\tfrac {1}{2}}\log _{2}{n}\approx 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 =}$

En sistemas de baja frecuencia, Dinur et al. (2003) demostraron que es NP-difícil aproximar la cobertura de conjuntos a mejor que . Si la conjetura de juegos únicos es verdadera, esto se puede mejorar a como lo demostraron Khot y Regev (2008). ${\displaystyle f-1-\epsilon }$ ${\displaystyle f-\epsilon }$

Trevisan (2001) demuestra que las instancias de cobertura de conjuntos con conjuntos de tamaño como máximo no se pueden aproximar a un factor mejor que a menos que P NP , lo que hace que la aproximación del algoritmo voraz sea esencialmente estricta en este caso. ${\displaystyle \Delta }$ ${\displaystyle \ln \Delta -O(\ln \ln \Delta )}$ ${\displaystyle =}$ ${\displaystyle \ln \Delta +1}$

Funda de juego con peso

Si se relaja el programa lineal entero para la cobertura de conjuntos ponderados indicado anteriormente, se puede utilizar un redondeo aleatorio para obtener una aproximación de factores. La cobertura de conjuntos no ponderados se puede adaptar al caso ponderado. ^[11] ${\displaystyle O(\log n)}$

Cobertura del conjunto fraccionario

Problemas relacionados

• Hitting set es una reformulación equivalente de Set Cover.
• La cobertura de vértice es un caso especial de Hitting Set.
• La cubierta de borde es un caso especial de cubierta de conjunto.
• 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 formas geométricas (por ejemplo, discos, rectángulos). ${\displaystyle \mathbb {R} ^{d}}$
• Conjunto de embalaje
• El problema de cobertura máxima consiste en 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 grafo 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 conjunto dominante es NP completo mediante una reducción a partir de la cobertura de conjuntos.
• El problema exacto de la cubierta es elegir una cubierta de conjunto sin ningún elemento incluido en más de un conjunto de cubierta.
• Cubierta del conjunto rojo y azul. ^[12]
• Secuestro encubierto .
• La dualización monótona es un problema computacional equivalente a enumerar todos los conjuntos mínimos de impacto o a enumerar todas las coberturas de conjuntos mínimos de una familia de conjuntos dada. ^[13]

Notas

1. Korte y Vygen 2012, pág. 414.
2. Vazirani (2001, pág. 15)
3. Vazirani (2001, pág. 108)
4. Vazirani (2001, págs. 110-112)
5. Nielsen, Frank (6 de septiembre de 2000). "Apuñalamiento rápido de cajas en grandes dimensiones" (PDF) . Theoretical Computer Science . 246 (1): 53–72. doi : 10.1016/S0304-3975(98)00336-3 . ISSN  0304-3975.
6. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990], "Ejercicio 35.3-3", Introducción a los algoritmos (3.ª ed.), MIT Press y McGraw-Hill, pág. 1122, ISBN 0-262-03384-4
7. Chvatal, V. (agosto de 1979), "Una heurística codiciosa para el problema de cobertura de conjuntos", Matemáticas de la investigación de operaciones , 4 (3): 233–235, doi :10.1287/moor.4.3.233, JSTOR  3689577
8. Karpinski y Zelikovsky 1998
9. Slavík Petr Un análisis riguroso del algoritmo voraz para la cobertura de conjuntos. STOC'96, páginas 435-441, doi :10.1145/237814.237991
10. Vazirani (2001, págs. 118-119)
11. Vazirani (2001, Capítulo 14)
12. Información., Sandia National Laboratories. Estados Unidos. Departamento de Energía. Estados Unidos. Departamento de Energía. Oficina de Asuntos Científicos y Técnicos (1999). On the Red-Blue Set Cover Problem. Estados Unidos. Departamento de Energía. OCLC  68396743.
13. Gainer-Dewar, Andrew; Vera-Licona, Paola (2017), "El problema de generación de conjuntos de impacto mínimo: algoritmos y computación", SIAM Journal on Discrete Mathematics , 31 (1): 63–100, arXiv : 1601.02939 , doi :10.1137/15M1055024, MR  3590650, S2CID  9240467

Referencias

• Alon, Noga ; Moshkovitz, Dana ; Safra, Shmuel (2006), "Construcción algorítmica de conjuntos para k-restricciones", ACM Trans. Algorithms , 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 de conjuntos", 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, vol. 40, American Mathematical Society, págs. 169-178, ISBN 9780821870846
• Lund, Carsten ; Yannakakis, Mihalis (1994), "Sobre la dificultad de aproximar 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 de bajo grado de probabilidad de error subconstante y una caracterización PCP de probabilidad de error subconstante de NP", STOC '97: Actas del vigésimo noveno simposio anual de la ACM sobre teoría de la computación , ACM, págs. 475–484, ISBN 978-0-89791-888-6.
• Dinur, Irit ; Steurer, David (2013), "Enfoque analítico para la repetición paralela", STOC '14: Actas del cuadragésimo sexto simposio anual de la 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), "Un algoritmo distribuido eficiente para calcular conjuntos de impactos mínimos" (PDF) , Actas del 25.º Taller internacional sobre principios de diagnóstico , Graz, Austria, doi :10.5281/zenodo.10037{{citation}}: CS1 maint: location missing publisher (link)
• Dinur, Irit ; Guruswami, Venkatesan ; Khot, Subhash ; Regev, Oded (2003), Un nuevo PCP multicapa y la dureza de la cubierta de vértices del hipergrafo, Association for Computing Machinery, págs. 595–601, doi :10.1145/780542.780629, ISBN 1581136749
• Khot, Subhash ; Regev, Oded (2008), La cobertura de vértices puede ser difícil de aproximar dentro de 2− ϵ {\displaystyle \epsilon } , Journal of Computer and System Sciences, págs. 335–349, doi :10.1016/j.jcss.2007.06.019
• Trevisan, Luca (2001), "Resultados de no aproximación para problemas de optimización en instancias de grado acotado", Actas del trigésimo tercer simposio anual de la ACM sobre teoría de la computación , Association for Computing Machinery, págs. 453–461, doi :10.1145/380752.380839, ISBN 1-58113-349-9

Enlaces externos

• Puntos de referencia con soluciones óptimas ocultas para la cobertura y el empaquetado de los sets y la determinación del ganador
• Un compendio de problemas de optimización NP - Cobertura del conjunto mínimo