Problema del conjunto de cobertura

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 \{1,2,...,m\} (llamado universo) y n conjuntos cuya unión comprende el universo, el set cover problem consiste en identificar el menor número de conjuntos cuya unión aun contiene todos los elementos del universo. Por ejemplo, sea U = \{1, 2, 3, 4, 5\} y los conjuntos S = \{\{1, 2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 5\}\}. Claramente, la unión de todos los conjuntos de S contiene todos los elementos de U. Sin embargo, podemos cubrir todos los elementos con el siguiente conjunto de elementos, con menor número de elementos: \{\{1, 2, 3\}, \{4, 5\}\}.

Definición formal[editar]

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

Problema de decisión de cobertura de conjuntos[editar]

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

Esta versión es un problema NP-completo.

Problema de optimización de cobertura de conjuntos[editar]

En el problema de optimización de cobertura de conjuntos, la entrada es un par (\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 linear entera[editar]

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

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

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

Algoritmo voraz[editar]

El algoritmo voraz para cobertura de conjuntos elije 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 H(s),[4] donde s es el tamaño del conjunto a cubrir y H(n) es el n-esimo número armónico:

 H(n) = \sum_{k=1}^{n} \frac{1}{k} \le \ln{n} +1
Ejemplo del algoritmo voraz para k=3

Hay un ejemplo estándar donde el algoritmo voraz obtiene un ratio de aproximación de \log_2(n)/2. El universo consta de n=2^{(k+1)}-2 elementos. El sistema de conjuntos consiste en k pares de conjuntos disjuntos S_1,\ldots,S_k con tamaños 2,4,8,\ldots,2^k respectivamente, así como dos conjuntos disjuntos adicionales T_0,T_2, cada uno de los cuales contiene la mitad de los elementos de cada S_i. Con estas entradas, el algoritmo voraz coge los conjuntos S_k,\ldots,S_1, en ese orden, mientras que la solución optima consistiría en escoger solamente T_0 y T_1.

Un ejemplo de estas entradas para 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[editar]

Si cada elemento se encuentra en 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[editar]

Lund y Yannakakis (1994) demostraron que el problema de cobertura de conjuntos no puede aproximarse en tiempo polinómico dentro de un factor de \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 \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 c\cdot\ln{n}, donde c es una constante, asumiendo que P\not=NP.[6] Un resultado similar, pero con mayor valor de c fue recientemente probado por Alon, Moshkovitz y Safra (2006).

Ejemplo[editar]

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[editar]

Sea:


 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:

Min \sum_{i=1}^{12} x_i

cumpliendo las siguientes restricciones:

x_1+x_2+x_3+x_5 \ge 1

x_2+x_1+x_5 \ge 1

x_3+x_1+x_4 +x_5+x_6+x_7+x_8\ge 1

x_4+x_3+x_5+x_6+x_{11}\ge 1

x_5+x_1+x_2+x_3+x_4+x_{10}+x_{11}\ge 1

x_6+x_3+x_4+x_8+x_{11}\ge 1

x_7+x_3+x_8+x_{12}\ge 1

x_8+x_3+x_6+x_7+x_9+x_{11}+x_{12}\ge 1

x_9+x_8+x_{10}+x_{11}+x_{12}\ge 1

x_{10}+x_5+x_9+x_{11}\ge 1

x_{11}+x_4+x_5+x_6+x_8+x_9+x_{10}\ge 1

x_{12}+x_7+x_8+x_9\ge 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[editar]

Una solución para este problema seria 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[editar]

Referencias[editar]

  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