b'\n_START_ARTICLE_\nProblema del conjunto de cobertura\n_START_PARAGRAPH_\nEl problema del Set Covering, tambi\xc3\xa9n conocido por sus siglas SCP es un problema cl\xc3\xa1sico en combinatoria, ciencias de la computaci\xc3\xb3n y teor\xc3\xada de la complejidad computacional. Es un problema que ha llevado al desarrollo de t\xc3\xa9cnicas fundamentales para el campo de los algoritmos de aproximaci\xc3\xb3n.\xe2\x80\x8b Tambi\xc3\xa9n es uno de los problemas de la Lista de 21 problemas NP-completos de Karp cuya NP-completitud fue demostrada en 1972._NEWLINE_Dado un conjunto de elementos  (llamado universo) y  conjuntos cuya uni\xc3\xb3n comprende el universo, el set cover problem consiste en identificar el menor n\xc3\xbamero de conjuntos cuya uni\xc3\xb3n aun contiene todos los elementos del universo. Por ejemplo, sea  y los conjuntos . Claramente, la uni\xc3\xb3n de todos los conjuntos de  contiene todos los elementos de . Sin embargo, podemos cubrir todos los elementos con el siguiente conjunto de elementos, con menor n\xc3\xbamero de elementos: .\n_START_SECTION_\nDefinici\xc3\xb3n formal\n_START_PARAGRAPH_\nFormalmente, se puede definir un problema de cobertura de conjuntos de la siguiente forma:_NEWLINE_Sea el universo  y la familia  de subconjuntos de , una cobertura es una subfamilia  de conjuntos cuya uni\xc3\xb3n es .\n_START_SECTION_\nProblema de decisi\xc3\xb3n de cobertura de conjuntos\n_START_PARAGRAPH_\nEn el problema de decisi\xc3\xb3n de cobertura de conjuntos, la entrada es un par  y un entero  y la pregunta es si existe un conjunto de cobertura de tama\xc3\xb1o  o menos._NEWLINE_Esta versi\xc3\xb3n es un problema NP-completo.\n_START_SECTION_\nProblema de optimizaci\xc3\xb3n de cobertura de conjuntos\n_START_PARAGRAPH_\nEn el problema de optimizaci\xc3\xb3n de cobertura de conjuntos, la entrada es un par  y la tarea es encontrar un conjunto de cobertura que use los menos conjuntos posibles._NEWLINE_Esta versi\xc3\xb3n es un problema NP-hard.\n_START_SECTION_\nSistemas de baja frecuencia\n_START_PARAGRAPH_\nSi cada elemento se encuentra en  conjuntos como m\xc3\xa1ximo, se puede encontrar una soluci\xc3\xb3n en tiempo polin\xc3\xb3mico que se aproxime al \xc3\xb3ptimo con dentro de un factor f usando relajaci\xc3\xb3n de programaci\xc3\xb3n lineal.\xe2\x80\x8b\n_START_SECTION_\nResultados poco \xc3\xb3ptimos\n_START_PARAGRAPH_\nLund\xc2\xa0y Yannakakis (1994) demostraron que el problema de cobertura de conjuntos no puede aproximarse en tiempo polin\xc3\xb3mico dentro de un factor de , a menos que NP tenga algoritmos de tiempo cuasi-polin\xc3\xb3mico. Feige (1998) mejor\xc3\xb3 este l\xc3\xadmite a  bajo las mismas condiciones, que pr\xc3\xa1cticamente coincide con el ratio de aproximaci\xc3\xb3n del algoritmo voraz. Raz\xc2\xa0y Safra (1997) estableci\xc3\xb3 la frontera inferior de , donde  es una constante, asumiendo que PNP.\xe2\x80\x8b Un resultado similar, pero con mayor valor de  fue recientemente probado por Alon, Moshkovitz y Safra (2006).\n_START_SECTION_\nEjemplo\n_START_PARAGRAPH_\nUna estaci\xc3\xb3n de bomberos tiene la capacidad de cubrir las emergencias tanto de su comuna como de las comunas adyacentes a ella, por ejemplo una estaci\xc3\xb3n construida en la comuna 1 (Figura 1) podr\xc3\xa1 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\xc3\xa9n cubiertas por al menos una estaci\xc3\xb3n (una o m\xc3\xa1s), minimizando el n\xc3\xbamero de estaciones construidas.\n_START_SECTION_\nModelo matem\xc3\xa1tico\n_START_PARAGRAPH_\nSea:_NEWLINE_podemos formular el problema de la siguiente forma:_NEWLINE_cumpliendo las siguientes restricciones:\n_START_SECTION_\nSoluci\xc3\xb3n\n_START_PARAGRAPH_\nUna soluci\xc3\xb3n para este problema seria construir estaciones en las comunas 5 y 8. Con un total de 2 estaciones construidas se lograr\xc3\xada cubrir las necesidades de todas las comunas del problema.'