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.
Dado un conjunto de elementos
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.
contiene todos los elementos de
de conjuntos cuya unión es
y la tarea es encontrar un conjunto de cobertura que use los menos conjuntos posibles.
[2] Esta ILP pertenece a la clase más general de ILPs para problemas de cobertura.
[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.
es el tamaño del conjunto a cubrir y
Hay un ejemplo estándar donde el algoritmo voraz obtiene un ratio de aproximación de
El sistema de conjuntos consiste en
pares de conjuntos disjuntos
respectivamente, así como dos conjuntos disjuntos adicionales
Con estas entradas, el algoritmo voraz coge los conjuntos
, en ese orden, mientras que la solución óptima consistiría en escoger solamente
Un ejemplo de estas entradas para
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.
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.
, a menos que NP tenga algoritmos de tiempo cuasi-polinómico.
Feige (1998) mejoró este límite a
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
es una constante, asumiendo que P
[6] Un resultado similar, pero con mayor valor de
fue recientemente probado por Alon, Moshkovitz y Safra (2006).
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.
se construye estación en la comuna i
podemos formular el problema de la siguiente forma:
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.
