En combinatoria y ciencias de la computación, los problemas de cobertura son problemas computacionales que preguntan si una determinada estructura combinatoria 'cubre' a otra, o qué tan grande debe ser la estructura para hacer eso.
En el contexto de la programación lineal, se puede pensar en cualquier programa lineal como un problema de cobertura si los coeficientes de la matriz de restricción, la función objetivo y el lado derecho no son negativos.
[1] Más precisamente, considere el siguiente programa lineal de enteros general: Tal programa lineal de enteros se llama problema de cobertura si
indica cuántos objetos de tipo
están satisfechos, se dice que
es una cobertura (las estructuras que se cubren dependen del contexto combinatorio).
Finalmente, una solución óptima para el programa lineal de enteros anterior es una cobertura de costo mínimo.
Más grande significa aquí que todos los componentes son al menos tan grandes como los de la marca dada y al menos uno es adecuadamente más grande.
En particular, en el problema de la cubierta del arco iris, cada uno de los objetos originales tiene un "color", y se requiere que la cubierta contenga exactamente un (o como mucho uno) objeto de cada color.
Se estudió la cobertura del arco iris, por ejemplo, para cubrir puntos por intervalos:[2] El problema es NP-duro (por reducción de SAT lineal).
Una noción más general es cobertura libre de conflictos.