Problemas de cobertura

En combinatoria e informática , 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 hacerlo. Los problemas de cobertura son problemas de minimización y generalmente programas lineales enteros , cuyos problemas duales se denominan problemas de empaquetamiento .

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

Los problemas de cobertura permiten que las primitivas de cobertura se superpongan; El proceso de cubrir algo con primitivas que no se superponen se llama descomposición .

Formulación general de programación lineal.

En el contexto de la programación lineal , se puede pensar en cualquier programa lineal de minimización como un problema de cobertura si los coeficientes en la matriz de restricciones , la función objetivo y el lado derecho no son negativos. ^[1] Más precisamente, considere el siguiente programa lineal entero general :

Un programa lineal entero de este tipo se denomina problema de cobertura si para todos y . $a_{ji},b_{j},c_{i}\geq 0$ $i=1,\dots ,n$ $j=1,\dots ,m$

Intuición: Supongamos que tenemos tipos de objetos y que cada objeto de tipo tiene un coste asociado de . El número indica cuántos objetos de tipo compramos. Si se satisfacen las restricciones se dice que es una cobertura (las estructuras que se cubren dependen del contexto combinatorio). Finalmente, una solución óptima para el programa lineal entero anterior es una cobertura de costo mínimo. $n$ $i$ $c_{i}$ $x_{i}$ $i$ $A\mathbf {x} \geq \mathbf {b}$ $\mathbf {x}$

Tipos de problemas de cobertura

Hay varios tipos de problemas de cobertura en teoría de grafos , geometría computacional y más; consulte Categoría: Problemas de cobertura . Se pueden encontrar otras versiones del problema relacionadas con el estocástico. ^[2]

Recubrimiento en redes de Petri

Para las redes de Petri , el problema de cobertura se define como la cuestión de si para una marca determinada existe una longitud de la red tal que se puede 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 indicada y al menos uno es propiamente más grande.

Cubierta de arcoiris

En algunos problemas de cobertura, la cobertura debe satisfacer algunos requisitos adicionales. En particular, en el problema de la cobertura del arco iris , cada uno de los objetos originales tiene un "color" y se requiere que la cobertura contenga exactamente un (o como máximo uno) objeto de cada color. Se estudió la cobertura del arco iris, por ejemplo, para cubrir puntos por intervalos : ^[3]

Hay un conjunto J de n intervalos coloreados en la recta real y un conjunto P de puntos en la recta real.
Un subconjunto Q de J se denomina conjunto arcoíris si contiene como máximo un único intervalo de cada color.
Un conjunto de intervalos J se denomina cobertura de P si cada punto de P está contenido en al menos un intervalo de Q.
El problema de la cobertura del arco iris es el problema de encontrar un conjunto de arcoíris Q que sea una cobertura de P.

El problema es NP-difícil (por reducción de SAT lineal ).

Cobertura sin conflictos

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

Hay un conjunto O de m objetos y un gráfico de conflicto G _O en O .
Un subconjunto Q de O se considera libre de conflictos si es un conjunto independiente en G _O , es decir, no hay dos objetos en Q que estén conectados por una arista en G _O.
Un conjunto arcoíris es un conjunto libre de conflictos en el caso especial en el que G _O está formado por camarillas disjuntas, donde cada camarilla representa un color.

La cobertura de conjuntos libre de conflictos es el problema de encontrar un subconjunto libre de conflictos de O que sea una cobertura de P. Banik, Panolan, Raman, Sahlot y Saurabh ^[5] demuestran lo siguiente para el caso especial en el que el gráfico de conflicto tiene arboricidad limitada :

Si el problema de cobertura geométrica es manejable con parámetros fijos (FPT), entonces el problema de cobertura 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 conflictos admite un algoritmo de aproximación similar en tiempo FPT.

Referencias

^ Vazirani, Vijay V. (2001). Algoritmos de aproximación . Springer-Verlag. ISBN 3-540-65367-8.^{: 112}
^ Douek-Pinkovich, Y., Ben-Gal, I. y Raviv, T. (2022). "El problema de la recopilación de pruebas estocásticas: modelos, enfoques de solución heurística y exacta" (PDF) . Revista europea de investigación operativa, 299 (2022), 945–959}.{{cite web}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
^ Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Mateo J.; Mitchell, Joseph SB; Simakov, Marina (11 de diciembre de 2018). "Seleccionar y cubrir puntos coloreados". Matemática Aplicada Discreta . 250 : 75–86. doi : 10.1016/j.dam.2018.05.011 . ISSN 0166-218X.
^ Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (1 de agosto de 2020). "Algoritmos de aproximación para problemas de cobertura geométricos libres de conflictos". Geometría Computacional . 89 : 101591. doi : 10.1016/j.comgeo.2019.101591. ISSN 0925-7721. S2CID 209959954.
^ Banik, Aritra; Panolan, Fahad; Raman, Venkatesh; Sahlot, Vibha; Saurabh, Saket (1 de enero de 2020). "Complejidad parametrizada de problemas de cobertura geométrica que tienen conflictos". Algorítmica . 82 (1): 1–19. doi :10.1007/s00453-019-00600-w. ISSN 1432-0541. S2CID 254027914.