Problema del conjunto de cobertura

El problema del Set Covering, también conocido por sus siglas SCP es un problema clásico en combinatoria, ciencias de la computación y teoría de la complejidad computacional. Es un problema que ha llevado al desarrollo de técnicas fundamentales para el campo de los algoritmos de aproximación.^[1]​ También es uno de los problemas de la Lista de 21 problemas NP-completos de Karp cuya NP-completitud fue demostrada en 1972.

Dado un conjunto de elementos ${\displaystyle \{1,2,...,m\}}$ (llamado universo) y ${\displaystyle n}$ conjuntos cuya unión comprende el universo, el problema del conjunto de cobertura consiste en identificar el menor número de conjuntos cuya unión aun contiene todos los elementos del universo. Por ejemplo, sea ${\displaystyle U=\{1,2,3,4,5\}}$ y los conjuntos ${\displaystyle S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}}$. Claramente, la unión de todos los conjuntos de ${\displaystyle S}$ contiene todos los elementos de ${\displaystyle U}$. Sin embargo, podemos cubrir todos los elementos con el siguiente conjunto de elementos, con menor número de elementos: ${\displaystyle \{\{1,2,3\},\{4,5\}\}}$.

Definición formal

Formalmente, se puede definir un problema de cobertura de conjuntos de la siguiente forma: Sea el universo ${\displaystyle {\mathcal {U}}}$  y la familia ${\displaystyle {\mathcal {S}}}$  de subconjuntos de ${\displaystyle {\mathcal {U}}}$ , una cobertura es una subfamilia ${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$  de conjuntos cuya unión es ${\displaystyle {\mathcal {U}}}$ .

Problema de decisión de cobertura de conjuntos

En el problema de decisión de cobertura de conjuntos, la entrada es un par ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$  y un entero ${\displaystyle k}$  y la pregunta es si existe un conjunto de cobertura de tamaño ${\displaystyle k}$  o menos.

Esta versión es un problema NP-completo.

Problema de optimización de cobertura de conjuntos

En el problema de optimización de cobertura de conjuntos, la entrada es un par ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$  y la tarea es encontrar un conjunto de cobertura que use los menos conjuntos posibles.

Esta versión es un problema NP-hard.

Formulación con programación lineal entera

El problema de cobertura de conjuntos se puede formular como la siguiente programación lineal de enteros (ILP por su nombre en inglés).^[2]​

minimizar	${\displaystyle \sum _{S\in {\mathcal {S}}}c(S)\cdot x_{S}}$		(minimizar el coste total)
cumpliendo	${\displaystyle \sum _{S\colon e\in S}x_{S}\geqslant 1}$	para todo ${\displaystyle e\in {\mathcal {U}}}$	(cubriendo todos los elementos del universo)
	${\displaystyle x_{S}\in \{0,1\}}$	para todo ${\displaystyle S\in {\mathcal {S}}}$ .	(todo conjunto, esté o no en conjunto de cobertura)

Esta ILP pertenece a la clase más general de ILPs para problemas de cobertura. La diferencia de integralidad de esta ILP es, como máximo, ${\displaystyle \scriptstyle \log n}$ , por lo tanto su relajación ofrece un algoritmo de aproximación de factor ${\displaystyle \scriptstyle \log n}$  para el problema de cobertura mínima de conjuntos (donde ${\displaystyle \scriptstyle n}$  es el tamaño del universo).^[3]​

Algoritmo voraz

El algoritmo voraz para cobertura de conjuntos elige conjuntos de acuerdo a una regla: en cada paso, elegir el conjunto que tiene el mayor número de elementos no elegidos. Se puede demostrar que este algoritmo consigue un ratio de aproximación de ${\displaystyle H(s)}$ ,^[4]​ donde ${\displaystyle s}$  es el tamaño del conjunto a cubrir y ${\displaystyle H(n)}$  es el ${\displaystyle n}$ -esimo número armónico:

${\displaystyle H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1}$ 

 

Hay un ejemplo estándar donde el algoritmo voraz obtiene un ratio de aproximación de ${\displaystyle \log _{2}(n)/2}$ . El universo consta de ${\displaystyle n=2^{(k+1)}-2}$  elementos. El sistema de conjuntos consiste en ${\displaystyle k}$  pares de conjuntos disjuntos ${\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_{2}}$ , cada uno de los cuales contiene la mitad de los elementos de cada ${\displaystyle S_{i}}$ . Con estas entradas, el algoritmo voraz coge los conjuntos ${\displaystyle S_{k},\ldots ,S_{1}}$ , en ese orden, mientras que la solución óptima consistiría en escoger solamente ${\displaystyle T_{0}}$  y ${\displaystyle T_{1}}$ .

Un ejemplo de estas entradas para ${\displaystyle k=3}$  se puede observar en la figura de la derecha.

Estos resultados tan poco cercanos a la solución óptima muestran que el algoritmo voraz es esencialmente el mejor algoritmo de aproximación en tiempo polinómico para el problema de cobertura de conjuntos, entre supuestos de complejidad plausible.

Sistemas de baja frecuencia

Si cada elemento se encuentra en ${\displaystyle f}$  conjuntos como máximo, se puede encontrar una solución en tiempo polinómico que se aproxime al óptimo con dentro de un factor f usando relajación de programación lineal.^[5]​

Resultados poco óptimos

Lund y Yannakakis (1994) demostraron que el problema de cobertura de conjuntos no puede aproximarse en tiempo polinómico dentro de un factor de ${\displaystyle {\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}}$ , a menos que NP tenga algoritmos de tiempo cuasi-polinómico. Feige (1998) mejoró este límite a ${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$  bajo las mismas condiciones, que prácticamente coincide con el ratio de aproximación del algoritmo voraz. Raz y Safra (1997) estableció la frontera inferior de ${\displaystyle c\cdot \ln {n}}$ , donde ${\displaystyle c}$  es una constante, asumiendo que P${\displaystyle \not =}$ NP.^[6]​ Un resultado similar, pero con mayor valor de ${\displaystyle c}$  fue recientemente probado por Alon, Moshkovitz y Safra (2006).

Ejemplo

 

Figura 1: Ejemplo de set covering para la cobertura de comunas.

Una estación de bomberos tiene la capacidad de cubrir las emergencias tanto de su comuna como de las comunas adyacentes a ella, por ejemplo una estación construida en la comuna 1 (Figura 1) podrá cubrir las emergencias de todo su vecindario, es decir, de la comuna 1, comuna 2, comuna 3 y comuna 5. Se necesitan construir tantas estaciones de bomberos como sea necesario para cubrir todas las comunas ante posibles emergencias, cuidando que todas las comunas estén cubiertas por al menos una estación (una o más), minimizando el número de estaciones construidas.

Modelo matemático

Sea:

${\displaystyle x_{i}={\begin{cases}1&{\mbox{se construye estación en la comuna i}}\\0&{\mbox{en otro caso}}\end{cases}}}$ 

podemos formular el problema de la siguiente forma:

${\displaystyle Min\sum _{i=1}^{12}x_{i}}$ 

cumpliendo las siguientes restricciones:

${\displaystyle x_{1}+x_{2}+x_{3}+x_{5}\geq 1}$ 

${\displaystyle x_{2}+x_{1}+x_{5}\geq 1}$ 

${\displaystyle x_{3}+x_{1}+x_{4}+x_{5}+x_{6}+x_{7}+x_{8}\geq 1}$ 

${\displaystyle x_{4}+x_{3}+x_{5}+x_{6}+x_{11}\geq 1}$ 

${\displaystyle x_{5}+x_{1}+x_{2}+x_{3}+x_{4}+x_{10}+x_{11}\geq 1}$ 

${\displaystyle x_{6}+x_{3}+x_{4}+x_{8}+x_{11}\geq 1}$ 

${\displaystyle x_{7}+x_{3}+x_{8}+x_{12}\geq 1}$ 

${\displaystyle x_{8}+x_{3}+x_{6}+x_{7}+x_{9}+x_{11}+x_{12}\geq 1}$ 

${\displaystyle x_{9}+x_{8}+x_{10}+x_{11}+x_{12}\geq 1}$ 

${\displaystyle x_{10}+x_{5}+x_{9}+x_{11}\geq 1}$ 

${\displaystyle x_{11}+x_{4}+x_{5}+x_{6}+x_{8}+x_{9}+x_{10}\geq 1}$ 

${\displaystyle x_{12}+x_{7}+x_{8}+x_{9}\geq 1}$ 

 

Solución óptima: En verde, las comunas cubiertas por la estación en 5; en amarillo, las cubiertas por la estación en 8; y en azul, las cubiertas 2 veces.

Solución

Una solución para este problema sería construir estaciones en las comunas 5 y 8. Con un total de 2 estaciones construidas se lograría cubrir las necesidades de todas las comunas del problema.

Véase también

• Problema de la cobertura de vértices
• Cobertura de aristas

Referencias

1. Vazirani (2001, p. 15)
2. Vazirani (2001, p. 108)
3. Vazirani (2001, pp. 110–112)
4. Chvatal, V. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research Vol. 4, No. 3 (Aug., 1979), pp. 233-235
5. Vazirani (2001, pp. 118-119)
6. Relación entre N y NP

• Alon, Noga; Moshkovitz, Dana; Safra, Shmuel (2006), «Algorithmic construction of sets for k-restrictions», ACM Trans. Algorithms (ACM) 2 (2): 153-177, ISSN 1549-6325, doi:10.1145/1150334.1150336 ..
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, Cambridge, Mass.: MIT Press and McGraw-Hill, pp. 1033-1038, ISBN 0-262-03293-7 .
• Feige, Uriel (1998), «A threshold of ln n for approximating set cover», Journal of the ACM (ACM) 45 (4): 634-652, ISSN 0004-5411, doi:10.1145/285055.285059 ..
• Lund, Carsten; Yannakakis, Mihalis (1994), «On the hardness of approximating minimization problems», Journal of the ACM (ACM) 41 (5): 960-981, ISSN 0004-5411, doi:10.1145/185675.306789 ..
• Raz, Ran; Safra, Shmuel (1997), «A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP», STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ACM, pp. 475-484, ISBN 978-0-89791-888-6 ..
• Vazirani, Vijay V. (2001), Approximation Algorithms, Springer-Verlag, ISBN 3-540-65367-8 .

•   Datos: Q1192100
•   Multimedia: Set cover problem