Problemas de cobertura

Tipo de problema computacional

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 lograrlo. Los problemas de cobertura son problemas de minimización y, por lo general, 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 conjuntos impactantes , y sus casos especiales, el problema de cobertura de vértices y el problema de cobertura de aristas .

Los problemas de cobertura permiten que los primitivos de cobertura se superpongan; el proceso de cubrir algo con primitivos que no se superponen se llama descomposición .

Formulación de programación lineal general

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 son no 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 . ${\displaystyle a_{ji},b_{j},c_{i}\geq 0}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle j=1,\dots ,m}$

Intuición: Supongamos que tenemos tipos de objeto y que cada objeto de tipo tiene un coste asociado de . El número indica cuántos objetos de tipo compramos. Si se cumplen 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 coste mínimo. ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle c_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$ ${\displaystyle A\mathbf {x} \geq \mathbf {b} }$ ${\displaystyle \mathbf {x} }$

Tipos de problemas de cobertura

Existen 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 estocásticas relacionadas con el problema. ^[2]

Cobertura en redes de Petri

En el caso de las redes de Petri , el problema de cobertura se define como la cuestión de si, para una marca dada, existe un recorrido de la red tal que se pueda alcanzar una marca mayor (o igual). Mayor significa aquí que todos los componentes son al menos tan grandes como los de la marca dada y al menos uno es apropiadamente mayor.

Cobertura de arcoiris

En algunos problemas de cobertura, la cobertura debe satisfacer algunos requisitos adicionales. En particular, en el problema de la cobertura de arco iris , cada uno de los objetos originales tiene un "color", y se requiere que la cobertura contenga exactamente un objeto (o como máximo un objeto) de cada color. La cobertura de arco iris se estudió, 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 iris 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 recubrimiento del arco iris es el problema de encontrar un conjunto arco iris Q que sea un recubrimiento de P.

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

Cobertura libre de 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 conflictos G _O en O .
• Un subconjunto Q de O se denomina libre de conflictos si es un conjunto independiente en G _O , es decir, no hay dos objetos en Q conectados por una arista en G _O .
• Un conjunto arco iris 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 libres 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 conflictos tiene arboricidad acotada :

• Si el problema de cobertura geométrica es tratable 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

1. Vazirani, Vijay V. (2001). Algoritmos de aproximación . Springer-Verlag. ISBN 3-540-65367-8.^:112
2. 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 exactos y heurísticos" (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)
3. Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph SB; Simakov, Marina (11 de diciembre de 2018). "Selección y cobertura de puntos coloreados". Matemáticas Aplicadas Discretas . 250 : 75–86. doi : 10.1016/j.dam.2018.05.011 . ISSN  0166-218X.
4. Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (1 de agosto de 2020). "Algoritmos de aproximación para problemas de cobertura sin conflictos geométricos". Geometría computacional . 89 : 101591. doi :10.1016/j.comgeo.2019.101591. ISSN  0925-7721. S2CID  209959954.
5. 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.