stringtranslate.com

Problema con la cubierta del conjunto

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 .

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.

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 dado anteriormente, excepto que la función objetivo a minimizar es , donde es el peso del conjunto .

La cobertura del conjunto fraccionario se describe mediante un programa idéntico al dado anteriormente, excepto que puede no ser un número entero, por lo que la última restricción se reemplaza por .

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.

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 los elementos a los 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 :

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]

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.

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]

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:

  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 .

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).

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.

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]

Cobertura del conjunto fraccionario

Problemas relacionados

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. 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

Enlaces externos