Establecer problema de portada

Problema clásico en combinatoria.

Ejemplo de un caso de problema de cobertura de conjunto.

El problema de la 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 } (llamado universo ) y una colección S de m subconjuntos cuya unión es igual al universo, el problema de cobertura de conjuntos es identificar la subcolección más pequeña de S cuya unión es igual a 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} }. Claramente la unión de S es U. Sin embargo, podemos cubrir todos los elementos con solo dos conjuntos: { {1, 2, 3}, {4, 5} }, ver imagen. Por lo tanto, la solución al problema de la cobertura del conjunto tiene el 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 conjuntos , la entrada es un par y un número entero ; La pregunta es si hay una funda ajustada de talla o menos. ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$ ${\displaystyle k}$ ${\displaystyle k}$
• En el problema de optimización de la 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 de la cobertura del conjunto es NP-completa . Es uno de los 21 problemas NP-completos de Karp que se demostró que son NP-completos en 1972. La versión de optimización/búsqueda de la cobertura del conjunto es NP-difícil . ^[1] 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 . ^[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 conjuntos con el peso más pequeño. La cobertura de juego habitual (no ponderada) corresponde a todos los juegos que tienen un peso de 1.

En el problema de cobertura de conjuntos fraccionarios , se permite seleccionar fracciones de conjuntos, en lugar de conjuntos completos. Una cobertura de conjunto fraccional 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 es al menos 1. El objetivo es encontrar una cobertura de conjunto fraccionario en la que la suma de fracciones sea lo más pequeña posible. Tenga en cuenta que una cobertura de conjunto (habitual) es equivalente a una cobertura de conjunto fraccionaria 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 cubierta del conjunto más pequeño tiene un tamaño de 2, por ejemplo, {{1, 2}, {2, 3}}. Pero existe una cobertura de conjunto fraccional 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 anterior, excepto que la función objetivo a minimizar es , donde está el peso del conjunto . ${\displaystyle \sum _{s\in {\mathcal {S}}}w_{s}x_{s}}$ ${\displaystyle w_{s}}$ ${\displaystyle s\in {\mathcal {S}}}$

La cobertura de conjuntos fraccionarios se describe mediante un programa idéntico al anterior, excepto que puede ser 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 cubrir problemas , ya que todos los coeficientes de la función objetivo y ambos lados de las restricciones no son negativos. La brecha de integralidad del ILP es como máximo (¿dónde está el tamaño del universo?). Se ha demostrado que su relajación proporciona un algoritmo de aproximación factorial para el problema de cobertura de conjuntos mínimos. ^[4] Consulte redondeo aleatorio#setcover para obtener una explicación detallada. ${\displaystyle \scriptstyle \log n}$ ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle \log n}$

Formulación de set de golpeo

La cobertura del set es equivalente al problema del set de bateo . Esto se ve al observar que una instancia de cobertura de conjuntos puede verse como un gráfico bipartito arbitrario , con el universo representado por vértices a la izquierda, los conjuntos representados por vértices a la derecha y los bordes que representan 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 del conjunto de aciertos.

En el campo de la geometría computacional , un conjunto de golpes para una colección de objetos geométricos también se llama conjunto de apuñalamiento o conjunto de perforación . ^[5]

Algoritmo codicioso

Existe un algoritmo codicioso para la aproximación en tiempo polinomial de la cobertura de conjuntos que elige conjuntos de acuerdo con una regla: en cada etapa, elija el conjunto que contenga 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 depósitos para priorizar los conjuntos. ^[6] Se logra un ratio de aproximación de , donde es el tamaño del conjunto a cubrir. ^[7] En otras palabras, encuentra una cobertura que puede ser varias veces mayor que 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 . 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 claro 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 se compone 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 consta solo de y . A la derecha se muestra un ejemplo de dicha entrada . ${\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 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 Resultados de inaproximabilidad a continuación), bajo supuestos de complejidad plausibles. Un análisis más detallado del algoritmo codicioso muestra que la relación de aproximación es exactamente . ^[9] ${\displaystyle \ln {n}-\ln {\ln {n}}+\Theta (1)}$

Sistemas de baja frecuencia

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

Si la restricción se reemplaza por para todo S en 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 de 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 polinómico dentro de un factor de , a menos que NP tenga algoritmos de tiempo cuasi-polinomiales . Feige (1998) mejoró este límite inferior bajo los mismos supuestos, lo que esencialmente coincide con el ratio de aproximación logrado 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 . Alon, Moshkovitz y Safra (2006) demostraron recientemente un resultado similar con un valor más alto de . Dinur y Steurer (2013) mostraron una inaproximabilidad óptima al demostrar que no se puede aproximar 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 =}$

Funda con peso

Al relajar el programa lineal entero para la cobertura de conjuntos ponderados indicado anteriormente, se puede utilizar el redondeo aleatorio para obtener una aproximación de factor. La funda del juego sin contrapeso se puede adaptar al estuche con contrapeso. ^[11] ${\displaystyle O(\log n)}$

Cubierta de juego fraccional

Problemas relacionados

• Golpear set es una reformulación equivalente de Set Cover.
• La cobertura Vertex es un caso especial de Hitting Set.
• La cubierta de borde 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 formas geométricas (p. ej., 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 del conjunto dominante. Se demostró que el problema del conjunto dominante era NP completo mediante una reducción de la cobertura del conjunto.
• El problema exacto de la cobertura consiste en elegir un conjunto de cobertura sin ningún elemento incluido en más de un conjunto de cobertura.
• Funda set rojo-azul. ^[12]
• Abducción de set-cover .
• La dualización monótona es un problema computacional equivalente a enumerar todos los conjuntos mínimos de impacto o enumerar todas las coberturas de conjuntos mínimos de una familia de conjuntos determinada. ^[13]

Notas

1. Korte y Vygen 2012, pag. 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). «Puñalada rápida de cajas de grandes dimensiones» (PDF) . Informática Teórica . 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. 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 exhaustivo del algoritmo codicioso para la cobertura de escenarios. 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., Laboratorios Nacionales Sandia. Estados Unidos. Departamento de Energía. Estados Unidos. Departamento de Energía. Oficina de Asuntos Científicos y Técnicos (1999). Sobre el problema de la cubierta del conjunto rojo-azul. Estados Unidos. Departamento de Energía. OCLC  68396743.
13. Gainer-Dewar, Andrew; Vera-Licona, Paola (2017), "El problema de generación de conjuntos de aciertos mínimos: algoritmos y cálculo", Revista SIAM de Matemáticas Discretas , 31 (1): 63–100, arXiv : 1601.02939 , doi : 10.1137/15M1055024, MR  3590650, S2CID  9240467

Referencias

• Alón, Noga ; Moshkovitz, Dana ; Safra, Shmuel (2006), "Construcción algorítmica de conjuntos para 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, vol. 40, Sociedad Estadounidense de Matemáticas, 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, corrió ; Safra, Shmuel (1997), "Una prueba de bajo grado de probabilidad de error subconstante y una caracterización de PCP de probabilidad de error subconstante de NP", STOC '97: Actas del vigésimo noveno simposio anual 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 informática , ACM, págs..
• 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, Nuño; Abreu, Rui (2014), "Un algoritmo distribuido eficiente para calcular conjuntos de aciertos 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)

enlaces externos

• Puntos de referencia con soluciones óptimas ocultas para cobertura de escenarios, embalaje de escenarios y determinación del ganador
• Un compendio de problemas de optimización NP: cobertura mínima del conjunto