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 .
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.
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.
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.
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 .
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 .
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 .
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.
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 :
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]
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 .
Los resultados de inaproximabilidad muestran que el algoritmo codicioso es esencialmente el mejor algoritmo de aproximación de tiempo polinómico 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]
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:
Encuentre una solución óptima O para el programa L utilizando algún método de tiempo polinomial para resolver programas lineales.
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 .
En sistemas de baja frecuencia, Dinur et al. (2003) demostraron que es NP-difícil aproximar la cobertura del conjunto a mejor que . Si la conjetura de los juegos únicos es cierta, esto puede mejorarse como lo demuestran Khot y Regev (2008).
Trevisan (2001) demuestra que las instancias de cobertura de conjuntos con conjuntos de tamaño como máximo no pueden aproximarse a un factor mejor que a menos que P NP , lo que hace que la aproximación del algoritmo codicioso sea esencialmente estricta en este caso.
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]
Cubierta de juego fraccional
Problemas relacionados
Golpear set es una reformulación equivalente 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).
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.
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
^ Korte y Vygen 2012, pag. 414.
^ Vazirani (2001, pág.15)
^ Vazirani (2001, pág.108)
^ Vazirani (2001, págs. 110-112)
^ 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.
^ 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
^ Vazirani (2001, págs. 118-119)
^ Vazirani (2001, capítulo 14)
^ 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.
^ 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.
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
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..
Khot, Subhash ; Regev, Oded (2008), La cobertura de Vertex podría 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 aproximabilidad para problemas de optimización en instancias de grados acotados", Actas del trigésimo tercer simposio anual de 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
Wikimedia Commons tiene medios relacionados con el problema de establecer la portada .
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