Problema de cobertura (combinatoria)

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. Los problemas de cobertura son problemas de minimización y, por lo general, programas lineales, cuyos problemas duales se denominan problemas de empaque.

Los ejemplos más destacados de problemas de cobertura son el problema de cobertura de conjuntos, que es equivalente al problema de acierto de conjuntos, y sus casos especiales, el problema de cobertura de vértices y el problema de cobertura de bordes.

Formulación de programación lineal general

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:

minimizar	${\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}$
sujeto a	${\displaystyle \sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ para }}j=1,\dots ,m}$
	${\displaystyle x_{i}\geq 0{\text{ para }}i=1,\dots ,n}$ .

Tal programa lineal de enteros se llama problema de cobertura si ${\displaystyle a_{ji},b_{j},c_{i}\geq 0}$  para todo ${\displaystyle i=1,\dots ,n}$  y ${\displaystyle j=1,\dots ,m}$ .

Intuición: suponga tener ${\displaystyle n}$  tipos de objeto y cada objeto de tipo ${\displaystyle i}$  tiene un costo asociado de ${\displaystyle c_{i}}$ . El número ${\displaystyle x_{i}}$  indica cuántos objetos de tipo ${\displaystyle i}$  compramos. Si las restricciones ${\displaystyle A\mathbf {x} \geq \mathbf {b} }$  están satisfechos, se dice que ${\displaystyle \mathbf {x} }$  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.

Tipos de problemas de cobertura

Hay varios tipos de problemas de cobertura en teoría de grafos, geometría computacional y más.

En el caso de las redes de Petri, por ejemplo, el problema de la cobertura se define como la cuestión de si para una marca determinada existe un recorrido de la red, de modo que se pueda alcanzar una marca mayor (o igual). 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.

Cobertura de arcoíris y cobertura libre de conflictos

En algunos problemas de cobertura, la cobertura debería satisfacer algunos requisitos adicionales. 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]​

• Hay un conjunto J de n intervalos de colores en la línea real y un conjunto P de puntos en la línea real.
• Un subconjunto Q de J se denomina conjunto de arco iris si contiene como máximo un intervalo único de cada color.
• Un conjunto de intervalos de J se llama un recubrimiento de P si cada punto en P está contenida en al menos un intervalo de Q.
• El problema que cubre arco iris es el problema de encontrar un conjunto de arco iris Q que es una cubierta de P.

El problema es NP-duro (por reducción de SAT lineal).

Una noción más general es cobertura libre de conflictos.^[3]​ En este problema:

• Hay un conjunto O de m objetos, y un conflicto-gráfico G_O en O.
• Un subconjunto Q de O se llama libre de conflictos si es un conjunto independiente en G_O, es decir, no hay dos objetos en Q están conectadas por un borde en G_O.
• Un conjunto de arcoíris es un conjunto libre de conflictos en el caso especial en el que G_O está formado por grupos separados, donde cada grupo representa un color.

El problema de la cobertura de conjunto libre de conflictos es el problema de encontrar un subconjunto libre de conflictos de O que es una cubierta de P. Banik, Panolan, Raman, Sahlot y Saurabh  prueban lo siguiente para el caso especial en el que el gráfico de conflicto tiene arboricidad limitada:

• Si el problema de la cubierta geométrica es tratable con parámetros fijos (FPT), entonces el problema de la cubierta geométrica libre de conflictos es FPT.
• Si el problema de cobertura geométrica admite un algoritmo de aproximación r, entonces el problema de cobertura geométrica libre de conflicto admite un algoritmo de aproximación similar en tiempo FPT.

Véase también

• Apareamiento (teoría de grafos)
• Cobertura de aristas
• Cobertura de vértices
• Conjunto independiente
• Problema del conjunto de cobertura
• Set packing

Referencias

1. Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8. ^:112
2. Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (11 de diciembre de 2018). «Selecting and covering colored points». Discrete Applied Mathematics (en inglés) 250: 75-86. ISSN 0166-218X. doi:10.1016/j.dam.2018.05.011. Consultado el 23 de marzo de 2021. 
3. Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (1 de agosto de 2020). «Approximation algorithms for geometric conflict free covering problems». Computational Geometry (en inglés) 89: 101591. ISSN 0925-7721. doi:10.1016/j.comgeo.2019.101591. Consultado el 23 de marzo de 2021.