Problema de la cubierta del conjunto

El problema de la cobertura de conjuntos es una cuestión clásica en combinatoria , informática , investigación operativa y teoría de la complejidad .

Dado un conjunto de elementos {1, 2, …, n } (en adelante denominado universo , que especifica todos los elementos posibles en 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 consiste en identificar la subcolección más pequeña de S cuya unión es igual al universo.

Por ejemplo, consideremos 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} } ‍ , ver 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${\displaystyle {\mathcal {U}}}$y una familia${\displaystyle {\mathcal {S}}}$de subconjuntos de${\displaystyle {\mathcal {U}}}$, una cubierta de conjunto es una subfamilia${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$de conjuntos cuya unión es${\displaystyle {\mathcal {U}}}$.

• En el problema de decisión de cobertura de conjuntos , la entrada es un par${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$y un número entero${\displaystyle k}$; la pregunta es si existe una cubierta fija de tamaño${\displaystyle k}$o menos.
• En el problema de optimización de cobertura de conjuntos , la entrada es un par${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$y la tarea consiste en encontrar una cobertura de conjuntos que utilice la menor cantidad de conjuntos.

La versión de decisión del problema de cobertura de conjuntos es NP-completa . Es uno de los 21 problemas NP-completos de Karp, cuya NP-completitud se demostró en 1972. La versión de optimización/búsqueda del problema de cobertura de conjuntos es NP-difícil . ^{[ 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 ]}

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 menor peso posible. La cobertura de conjuntos habitual (sin ponderar) corresponde a que todos los conjuntos tengan 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 conjuntos fraccionarios es una asignación de una fracción (un número en [0,1]) a cada conjunto en${\displaystyle {\mathcal {S}}}$, de tal manera 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 conjuntos fraccionaria en la que la suma de fracciones sea lo más pequeña posible. Nótese que una cobertura de conjuntos (usual) es equivalente a una cobertura de conjuntos 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, consideremos 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 hay una cobertura de conjuntos fraccionaria de tamaño 1.5, en la que se toma una fracción de 0.5 de cada conjunto.

En el problema de cobertura de conjuntos con capacidad , cada conjunto${\displaystyle s\in {\mathcal {S}}}$está asociado con una capacidad${\displaystyle c_{S}}$que indica el número de elementos a los que puede proporcionar cobertura. El objetivo es determinar la forma óptima de seleccionar conjuntos de manera que cada elemento reciba la cobertura que requiere.

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

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

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

La cobertura de conjuntos fraccionarios se describe mediante un programa idéntico al dado anteriormente, excepto que${\displaystyle x_{s}}$puede no ser un número entero, por lo que la última restricción se reemplaza por${\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${\displaystyle \scriptstyle \log n}$(dónde${\displaystyle \scriptstyle n}$es el tamaño del universo). Se ha demostrado que su relajación efectivamente da un factor-${\displaystyle \scriptstyle \log n}$Algoritmo de aproximación para el problema de cobertura de conjuntos mínimos. ^{[ 4 ]} Consulte setcover para obtener una explicación detallada.

El problema de cobertura de conjuntos es equivalente al problema de conjuntos de colisión. Un subconjunto${\displaystyle H}$de${\displaystyle U}$se llama set de ataque cuando${\displaystyle H\cap S_{j}\neq \emptyset }$a pesar de${\displaystyle 1\leq j\leq m}$(es decir,${\displaystyle H}$interseca o “golpea” todos los subconjuntos en${\displaystyle S}$). El problema del conjunto de impacto consiste en encontrar un conjunto de impacto mínimo${\displaystyle H}$para un dado${\displaystyle U}$y${\displaystyle S}$.

Para demostrar que los problemas son equivalentes, para un universo${\displaystyle U}$de tamaño${\displaystyle n}$y colección de conjuntos${\displaystyle S}$de tamaño${\displaystyle m}$construir${\displaystyle U'=\{1,2,\ldots ,m\}}$y ${\displaystyle S'_{i}=\{j\mid i\in S_{j}\}}$Luego, una cubierta del set${\displaystyle C}$de${\displaystyle S}$es equivalente a un set de bateo${\displaystyle H'}$de${\displaystyle U'}$dónde${\displaystyle S_{j}\in C\iff j\in H'}$y viceversa.

Esta equivalencia también puede visualizarse representando el problema como un grafo bipartito de${\displaystyle n+m}$vértices, con${\displaystyle n}$vértices de la izquierda que representan elementos de${\displaystyle U}$, y${\displaystyle m}$vértices a la derecha que representan elementos de${\displaystyle S}$y aristas que representan la pertenencia a un conjunto (es decir, hay una arista entre el${\displaystyle i}$-ésimo vértice a la izquierda y el${\displaystyle j}$-ésimo vértice de la derecha si y solo si.${\displaystyle i\in S_{j}}$). Entonces, una cobertura de conjunto es un subconjunto${\displaystyle C}$de vértices derechos de tal manera que cada vértice izquierdo sea adyacente a al menos un miembro de${\displaystyle C}$, mientras que un conjunto de golpes es un subconjunto${\displaystyle H}$de vértices izquierdos de tal manera que cada vértice derecho sea adyacente a al menos un miembro de${\displaystyle H}$Estas definiciones son exactamente las mismas, excepto que izquierda y derecha están intercambiadas. Pero no hay nada especial en los lados del grafo bipartito; podríamos haber puesto los elementos de${\displaystyle U}$en el lado derecho y los elementos de ${\displaystyle S}$En el lado izquierdo, se crea un gráfico que es una imagen especular del descrito anteriormente. Esto demuestra que cubrir conjuntos en el gráfico original equivale a alcanzar conjuntos en el gráfico reflejado, y viceversa.

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 ]}

Existe un algoritmo voraz para la aproximación en tiempo polinomial de la cobertura de conjuntos que elige conjuntos según una regla: en cada etapa, elige el conjunto que contiene el mayor número de elementos no cubiertos. Este método se puede implementar en tiempo lineal en la suma de los tamaños de los conjuntos de entrada, utilizando una cola de cubetas para priorizar los conjuntos. ^{[ 6 ]} Logra una razón de aproximación de${\displaystyle H(s)}$, dónde${\displaystyle s}$es el tamaño del conjunto a cubrir. ^{[ 7 ] [ 8 ] [ 9 ]} En otras palabras, encuentra una cobertura que puede ser${\displaystyle H(n)}$veces mayor que el mínimo, donde${\displaystyle H(n)}$es el${\displaystyle n}$-ésimo número armónico : $${\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${\displaystyle H(s^{\prime })}$dónde${\displaystyle s^{\prime }}$es el conjunto de cardinalidad máxima de${\displaystyle S}$. Para${\displaystyle \delta -}$Sin embargo, en casos densos existe una${\displaystyle c\ln {m}}$-algoritmo de aproximación para cada${\displaystyle c>0}$. ^{[ 10 ]}

Existe un ejemplo estándar en el que el algoritmo voraz logra una relación de aproximación de${\displaystyle \log _{2}(n)/2}$. El universo consta de${\displaystyle n=2^{(k+1)}-2}$elementos. El sistema de conjuntos consta de${\displaystyle k}$conjuntos disjuntos por pares${\displaystyle S_{1},\ldots ,S_{k}}$con tamaños${\displaystyle 2,4,8,\ldots ,2^{k}}$respectivamente, así como dos conjuntos disjuntos adicionales${\displaystyle T_{0},T_{1}}$, cada uno de los cuales contiene la mitad de los elementos de cada${\displaystyle S_{i}}$. Con esta entrada, el algoritmo voraz toma los conjuntos ${\displaystyle S_{k},\ldots ,S_{1}}$, en ese orden, mientras que la solución óptima consiste únicamente en${\displaystyle T_{0}}$y${\displaystyle T_{1}}$. Un ejemplo de dicha entrada para${\displaystyle k=3}$Se muestra en la imagen de la derecha.

Los resultados de inaproximabilidad muestran que el algoritmo voraz es esencialmente el mejor algoritmo de aproximación en tiempo polinomial posible para la cobertura de conjuntos hasta términos de orden inferior (ver Resultados de inaproximabilidad a continuación), bajo supuestos de complejidad plausibles. Un análisis más riguroso para el algoritmo voraz muestra que la razón de aproximación es exactamente${\displaystyle \ln {n}-\ln {\ln {n}}+\Theta (1)}$. ^{[ 11 ]}

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

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

1. Encuentra una solución óptima O para el programa L utilizando algún método de tiempo polinomial para resolver programas lineales.
2. Seleccione 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 . ^{[ 12 ]}

Cuando${\displaystyle n}$se refiere al tamaño del universo, Lund y Yannakakis (1994) demostraron que la cobertura de conjuntos no se puede aproximar en tiempo polinomial con un factor de${\displaystyle {\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}}$, a menos que NP tenga algoritmos de tiempo cuasi-polinomial . Feige (1998) mejoró esta cota inferior a${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$bajo los mismos supuestos, que esencialmente coincide con la razón de aproximación lograda por el algoritmo voraz. Raz y Safra (1997) establecieron una cota inferior de${\displaystyle c\cdot \ln {n}}$, dónde${\displaystyle c}$es una cierta constante, bajo el supuesto más débil de que P${\displaystyle \not =}$NP . Un resultado similar con un valor más alto de${\displaystyle c}$fue demostrado recientemente por Alon, Moshkovitz y Safra (2006) . Dinur y Steurer (2013) demostraron la inaproximabilidad óptima al probar que no se puede aproximar a${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$a menos que P${\displaystyle =}$NP .

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

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

El algoritmo voraz para el problema de cobertura de conjuntos ponderados ^{[ 7 ]} generaliza directamente la versión no ponderada. Dado un universo${\displaystyle {\mathcal {U}}}$y una familia${\displaystyle {\mathcal {S}}}$de subconjuntos de${\displaystyle {\mathcal {U}}}$donde cada conjunto${\displaystyle S\in {\mathcal {S}}}$Se le asigna un peso no negativo (costo), el algoritmo mantiene el subconjunto de elementos que aún no están cubiertos. Inicialmente, todos los elementos de${\displaystyle {\mathcal {U}}}$se descubren. En cada iteración, el algoritmo selecciona un conjunto${\displaystyle S\in {\mathcal {S}}}$que minimiza la relación entre su peso y el número de elementos actualmente no cubiertos que contiene. El conjunto seleccionado se agrega a la solución y todos los elementos contenidos en él se marcan como cubiertos. Este proceso se repite hasta que todos los elementos de${\displaystyle {\mathcal {U}}}$están cubiertos. Se sabe que el algoritmo voraz produce una solución cuyo peso total es como máximo un factor de${\displaystyle H(n)}$veces la solución óptima, donde${\displaystyle H(n)}$denota el${\displaystyle n}$-ésimo número armónico y${\displaystyle n=|{\mathcal {U}}|}$.

Para sistemas de baja frecuencia, donde cada elemento está contenido en como máximo${\displaystyle f}$conjuntos, el algoritmo de redondeo LP determinista obtiene un${\displaystyle f}$-aproximación. ^{[ 13 ]} Comienza con la solución óptima a la relajación de programación lineal del problema enunciado anteriormente . Conjuntos cuyo valor fraccional excede${\displaystyle 1/f}$se seleccionan para formar una solución entera.

El algoritmo primal-dual para el problema de cobertura de conjuntos es un método iterativo que construye soluciones factibles para los programas lineales primal y dual simultáneamente. Comenzando con todas las variables duales establecidas en cero, el algoritmo incrementa repetidamente las variables duales correspondientes a los elementos no cubiertos de manera uniforme, hasta que la restricción dual de algún conjunto se vuelve ajustada (es decir, la suma de las variables duales para los elementos del conjunto es igual a su costo). Este conjunto ajustado se agrega a la solución primal, cubriendo los elementos correspondientes. El proceso continúa hasta que todos los elementos estén cubiertos. El algoritmo garantiza una razón de aproximación de${\displaystyle f}$, dónde${\displaystyle f}$es el número máximo de conjuntos a los que pertenece cualquier elemento. ^{[ 14 ]}

El redondeo aleatorio es una técnica de aproximación para el problema de cobertura de conjuntos ponderados que utiliza la solución de la relajación de programación lineal. Sea${\displaystyle {x_{S}^{*}}}$ser una solución fraccionaria óptima para la relajación LP. Cada conjunto${\displaystyle S\in {\mathcal {S}}}$se incluye independientemente en la cobertura con probabilidad${\displaystyle x_{S}^{*}}$Por linealidad de la esperanza, el costo esperado de los conjuntos elegidos es igual al óptimo de LP. La probabilidad de que algún elemento permanezca sin cubrir puede hacerse arbitrariamente pequeña escalando las probabilidades o redondeando repetidamente. Usando límites de concentración estándar, esto produce una cobertura de conjunto factible cuyo costo esperado está dentro de un${\displaystyle O(\log n)}$factor de la solución óptima, donde${\displaystyle n}$es el tamaño del universo.

Las referencias se pueden encontrar en ^{[ 15 ]} y ^{[ 16 ]} .

• El juego de golpear el set es una reformulación equivalente de Set Cover.
• La cobertura de vértices es un caso especial de conjunto de colisión.
• La cobertura de bordes es un caso especial de cobertura de conjunto.
• La cobertura de conjuntos geométricos es un caso especial de cobertura de conjuntos cuando el universo es un conjunto de puntos en${\displaystyle \mathbb {R} ^{d}}$y los conjuntos se generan por la intersección del universo y las formas geométricas (por ejemplo, discos, rectángulos).
• El problema del empaquetamiento de conjuntos consiste en seleccionar el número máximo de conjuntos que son disjuntos dos a dos.
• El problema de cobertura máxima consiste en elegir como máximo${\displaystyle k}$conjuntos para abarcar la mayor cantidad de elementos posible.
• El problema del conjunto dominante consiste en seleccionar un conjunto de vértices (el conjunto dominante) en un grafo de tal manera 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 es NP-completo mediante una reducción a partir del problema de la cobertura de conjuntos.
• El problema exacto de la cubierta consiste en elegir una cubierta de conjunto que no incluya ningún elemento en más de un conjunto de cubierta.
• El problema de cobertura de conjuntos rojo-azul es una generalización del problema de cobertura de conjuntos donde los elementos del universo están coloreados de rojo o azul, y el objetivo es seleccionar una subcolección de los conjuntos dados que cubra todos los elementos azules y al mismo tiempo cubra el número mínimo de elementos rojos. ^{[ 17 ]}
• La abducción de conjuntos y coberturas es un problema relacionado en el que, dado un conjunto de observaciones y un conjunto de hipótesis, el objetivo es seleccionar un subconjunto de las hipótesis cuyos efectos incluyan todas las observaciones.
• La dualización monótona es un problema computacional equivalente a enumerar todos los conjuntos mínimos de intersección o enumerar todas las coberturas mínimas de conjuntos de una familia de conjuntos dada. ^{[ 18 ]}

• 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 Localización de Instalaciones , vol.  40, American Mathematical Society, pp. 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 con probabilidad de error subconstante y una caracterización PCP de NP con probabilidad de error subconstante", 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 el cálculo de conjuntos mínimos de coincidencias" (PDF) , Actas del 25.º Taller Internacional sobre Principios de Diagnóstico , Graz, Austria, doi : 10.5281/zenodo.10037{{citation}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
• Dinur, Irit ; Guruswami, Venkatesan ; Khot, Subhash ; Regev, Oded (2003), Un nuevo PCP multicapa y la dificultad de la cobertura de vértices de hipergrafos , Association for Computing Machinery, pp. 595–601 , doi : 10.1145/780542.780629 , ISBN  1581136749
• Khot, Subhash ; Regev, Oded (2008), La cobertura de vértices podría ser difícil de aproximar dentro de 2−${\displaystyle \epsilon }$, Revista de Ciencias de la Computación y de Sistemas, 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, pp. 453–461 , doi : 10.1145/380752.380839 , ISBN  1-58113-349-9

• Puntos de referencia con soluciones óptimas ocultas para la cobertura de sets, el empaquetamiento de sets y la determinación del ganador. Archivado el 25/07/2017 en Wayback Machine.
• Compendio de problemas de optimización NP: Cobertura mínima de conjuntos