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 . [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 del conjunto es identificar la subcolección más pequeña decuya unión es igual al universo. Por ejemplo, considere el universo y la colección de decorados . Claramente la unión de es . Sin embargo, podemos cubrir todos los elementos con el siguiente número menor de conjuntos:.
Más formalmente, dado un universo y una familia de subconjuntos de , una portada es una subfamilia de conjuntos cuya unión es . En el conjunto que cubre el problema de decisión , la entrada es un par y un entero ; la pregunta es si existe una cobertura de tamaño determinadao menos. En el problema de optimización de cobertura del conjunto , 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-complete , y la versión de optimización / búsqueda de la cobertura del conjunto es NP-hard . [2]
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). [3]
minimizar | (minimizar el número de juegos) | ||
sujeto a | para todos | (cubre todos los elementos del universo) | |
para todos . | (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 da un factor- algoritmo de aproximación para el problema de cobertura del conjunto mínimo (dondees el tamaño del universo). [4]
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.
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 el tiempo lineal en la suma de tamaños de los conjuntos de entrada, utilizando una cola de depósito para priorizar los conjuntos. [5] Alcanza una relación de aproximación de, dónde es el tamaño del conjunto a cubrir. [6] En otras palabras, encuentra una cubierta que puede ser veces tan grande como el mínimo, donde es el -th armónico número :
Este algoritmo codicioso en realidad logra una relación de aproximación de dónde es el conjunto de cardinalidad máxima de . Paracasos densos, sin embargo, existe un -algoritmo de aproximación para cada . [7]
Hay un ejemplo estándar en el que el algoritmo codicioso logra una relación de aproximación de . El universo consta deelementos. El sistema de conjuntos consta de conjuntos disjuntos por pares con tallas 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 codicioso toma los conjuntos, en ese orden, mientras que la solución óptima consiste solo en y . Un ejemplo de tal entrada para se muestra a la derecha.
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. [8]
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 es reemplazado por para todos los S enen 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:
- 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 . [9]
Resultados de inapropiabilidad
Cuándo se refiere al tamaño del universo, Lund y Yannakakis (1994) mostraron que la cobertura del conjunto no se puede aproximar en tiempo polinomial dentro de un factor de, a menos que NP tenga algoritmos de tiempo cuasi-polinomiales . Feige (1998) mejoró este límite inferior parabajo 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, dónde es una cierta constante, bajo el supuesto más débil de que PNP . Un resultado similar con un valor más alto defue probado recientemente por Alon, Moshkovitz & Safra (2006) . Dinur y Steurer (2013) mostraron una inaproximación óptima al demostrar que no se puede aproximar aa menos que PNP .
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 un-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. [10]
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 conjunto geométrico es un caso especial de cobertura de conjunto cuando el universo es un conjunto de puntos en y los conjuntos son inducidos por la intersección del universo y las formas geométricas (por ejemplo, discos, rectángulos).
- 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 de juego sin ningún elemento incluido en más de un juego de cubierta.
Notas
- ^ Vazirani (2001 , p. 15)
- ^ Korte y Vygen 2012 , p. 414.
- ↑ Vazirani (2001 , p. 108)
- ^ Vazirani (2001 , págs. 110-112)
- ^ 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
- ^ Chvatal, V.Una heurística codiciosa para el problema de cobertura de conjuntos . Matemáticas de la investigación operativa Vol. 4, núm. 3 (agosto de 1979), págs.
- ^ Karpinski y Zelikovsky 1998
- ^ Slavík Petr Un análisis riguroso del algoritmo codicioso para la cobertura del set . STOC'96, páginas 435-441, doi : 10.1145 / 237814.237991
- ^ Vazirani (2001 , págs. 118-119)
- ↑ Vazirani (2001 , Capítulo 14)
Referencias
- Alon, 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 , 40 , págs. 169-178, ISBN 9780821870846 Parámetro desconocido
|book-title=
ignorado ( ayuda ) - 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 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) , Graz, Austria, doi : 10.5281 / zenodo.10037 Parámetro desconocido
|book-title=
ignorado ( ayuda )
enlaces externos
- Puntos de referencia con soluciones óptimas ocultas para la cobertura del set, el embalaje del set y la determinación del ganador
- Un compendio de problemas de optimización de NP - Cobertura mínima del conjunto