Problema del conjunto de cobertura

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

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]

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.

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]

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

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.

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

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