LISTA DE PROBLEMAS

El problema de la cobertura del conjunto es una pregunta clásica en combinatoria , informática , investigación de operaciones y teoría de la complejidad . Es uno de los 21 problemas de NP completo de Karp que se demostró que era NP completo en 1972.

Es un problema "cuyo estudio ha llevado al desarrollo de técnicas fundamentales para todo el campo" de los algoritmos de aproximación . ^[1]

Dado un conjunto de elementos $${\ displaystyle \ {1,2, ..., n \}}(llamado el universo ) y una colección$${\ displaystyle S} de $${\ displaystyle m}conjuntos cuya unión es igual al universo, el problema de la cubierta del conjunto es identificar la subcolección más pequeña de$${\ displaystyle S}cuya unión es igual al universo. Por ejemplo, considere el universo$${\ displaystyle U = \ {1,2,3,4,5 \}} y la colección de conjuntos $${\ displaystyle S = \ {\ {1,2,3 \}, \ {2,4 \}, \ {3,4 \}, \ {4,5 \} \}}. Claramente la unión de$${\ displaystyle S} es $${\ displaystyle U}. Sin embargo, podemos cubrir todos los elementos con el siguiente número menor de conjuntos:$${\ displaystyle \ {\ {1,2,3 \}, \ {4,5 \} \}}.

Más formalmente, dado un universo $${\ displaystyle {\ mathcal {U}}} y una familia $${\ displaystyle {\ mathcal {S}}} de subconjuntos de $${\ displaystyle {\ mathcal {U}}}, una portada es una subfamilia$${\ displaystyle {\ mathcal {C}} \ subseteq {\ mathcal {S}}} de conjuntos cuya unión es $${\ displaystyle {\ mathcal {U}}}. En el problema de decisión de cobertura del conjunto , la entrada es un par$${\ displaystyle ({\ mathcal {U}}, {\ mathcal {S}})} y un entero $${\ displaystyle k}; la pregunta es si hay una cobertura de tamaño establecida$${\ displaystyle k}o menos. En el conjunto que cubre el problema de optimización , la entrada es un par$${\ displaystyle ({\ mathcal {U}}, {\ mathcal {S}})}, y la tarea es encontrar una cobertura de conjunto que use la menor cantidad de conjuntos.

La versión de decisión de la cobertura del conjunto es NP-completa , y la versión de optimización / búsqueda de la cobertura del conjunto es NP-hard . ^[2]

Si a cada conjunto se le asigna un costo, se convierte en un problema de cobertura de conjunto ponderado .

Formulación de programa lineal entero [ editar ]

El problema de cobertura de conjunto mínimo se puede formular como el siguiente programa lineal entero (ILP). ^[3]

minimizar	$${\ displaystyle \ sum _ {S \ in {\ mathcal {S}}} x_ {S}}		(minimizar el número de juegos)
sujeto a	$${\ displaystyle \ sum _ {S \ colon e \ in S} x_ {S} \ geqslant 1}	para todos $${\ displaystyle e \ en {\ mathcal {U}}}	(cubre todos los elementos del universo)
	$${\ displaystyle x_ {S} \ in \ {0,1 \}}	para todos $${\ displaystyle S \ en {\ mathcal {S}}}.	(cada conjunto está en la cubierta del conjunto o no)

Este ILP pertenece a la clase más general de ILP para cubrir problemas . La brecha de integralidad de este ILP es como máximo$${\ displaystyle \ scriptstyle \ log n}, por lo que su relajación da un factor$${\ displaystyle \ scriptstyle \ log n} algoritmo de aproximación para el problema de cobertura de conjunto mínimo (donde$${\ displaystyle \ scriptstyle n}es el tamaño del universo). ^[4]

En la cubierta del conjunto ponderado, los conjuntos tienen pesos asignados. Denota el peso del conjunto$${\ displaystyle S \ en {\ mathcal {S}}} por $${\ displaystyle w_ {S}}. Entonces, el programa lineal entero que describe la cobertura del conjunto ponderado es idéntico al dado anteriormente, excepto que la función objetivo para minimizar es$${\ displaystyle \ sum _ {S \ in {\ mathcal {S}}} w_ {S} x_ {S}}.

Formulación de conjunto de golpes [ editar ]

La cobertura del conjunto es equivalente al problema del conjunto de golpes . Esto se observa al observar que una instancia de cobertura de conjuntos se puede ver como un gráfico bipartito arbitrario , con conjuntos representados por vértices a la izquierda, el universo representado por vértices a la derecha y bordes que representan la inclusión de elementos en conjuntos. La tarea es encontrar un subconjunto de cardinalidad mínima de vértices izquierdos que cubra todos los vértices derechos. En el problema del conjunto de golpes, el objetivo es cubrir los vértices izquierdos utilizando un subconjunto mínimo de los vértices derechos. Por lo tanto, la conversión de un problema a otro se logra intercambiando los dos conjuntos de vértices.

Algoritmo codicioso [ editar ]

Existe un algoritmo codicioso para la aproximación del tiempo polinómico de la cobertura de conjuntos que elige conjuntos de acuerdo con una regla: en cada etapa, elija el conjunto que contenga la mayor cantidad de elementos descubiertos. Se puede demostrar ^[5] que este algoritmo logra una relación de aproximación de$${\ displaystyle H (s)}, dónde $${\ displaystyle s}es el tamaño del conjunto a cubrir. En otras palabras, encuentra una cobertura que puede ser$${\ displaystyle H (n)} veces más grande que el mínimo, donde $${\ displaystyle H (n)} es el $${\ displaystyle n}-th número armónico :

$${\ displaystyle H (n) = \ sum _ {k = 1} ^ {n} {\ frac {1} {k}} \ leq \ ln {n} +1}

Este algoritmo codicioso en realidad logra una relación de aproximación de $${\ displaystyle H (s ^ {\ prime})} dónde $${\ displaystyle s ^ {\ prime}} es el conjunto de cardinalidad máxima de $${\ displaystyle S}. por$${\ displaystyle \ delta -}instancias densas, sin embargo, existe un $${\ displaystyle c \ ln {m}}algoritmo de aproximación para cada {\ displaystyle c> 0}. ^[6]

Ejemplo apretado para el algoritmo codicioso con k = 3

Hay un ejemplo estándar en el que el algoritmo codicioso logra una relación de aproximación de $${\ displaystyle \ log _ {2} (n) / 2}. El universo consiste en$${\ displaystyle n = 2 ^ {(k + 1)} - 2}elementos. El sistema establecido consta de$${\ displaystyle k} conjuntos disjuntos por pares $${\ displaystyle S_ {1}, \ ldots, S_ {k}} con tamaños $${\ displaystyle 2,4,8, \ ldots, 2 ^ {k}} respectivamente, así como dos conjuntos disjuntos adicionales $${\ displaystyle T_ {0}, T_ {1}}, cada uno de los cuales contiene la mitad de los elementos de cada $${\ displaystyle S_ {i}}. En esta entrada, el algoritmo codicioso toma los conjuntos $${\ displaystyle S_ {k}, \ ldots, S_ {1}}, en ese orden, mientras que la solución óptima consiste solo en $${\ displaystyle T_ {0}} y $${\ displaystyle T_ {1}}. Un ejemplo de tal entrada para$${\ displaystyle k = 3} se muestra a la derecha.

Los resultados de inaproximabilidad muestran que el algoritmo codicioso es esencialmente el mejor algoritmo de aproximación de tiempo polinomial posible para la cobertura del conjunto hasta los términos de orden inferior (ver los resultados de inaproximabilidad a continuación), bajo supuestos de complejidad plausible. Un análisis más estricto para el algoritmo codicioso muestra que la relación de aproximación es exactamente$${\ displaystyle \ ln {n} - \ ln {\ ln {n}} + \ Theta (1)}. ^[7]

Sistemas de baja frecuencia [ editar ]

Si cada elemento aparece en la mayoría de los conjuntos f , entonces se puede encontrar una solución en el tiempo polinomial que se aproxima al óptimo dentro de un factor de f usando relajación LP .

Si la restricción $${\ displaystyle x_ {S} \ in \ {0,1 \}} es reemplazado por $${\ displaystyle x_ {S} \ geq 0}para todos los S en$${\ displaystyle {\ mathcal {S}}}en el programa lineal entero que se muestra arriba , se convierte en un programa lineal L (no entero) . El algoritmo se puede describir de la siguiente manera:

1. Encuentre una solución óptima O para el programa L utilizando algún método de tiempo polinómico para resolver programas lineales.
2. Recoger todos los conjuntos S para el que la variable correspondiente x _S tiene un valor de al menos 1 / f en la solución de O . ^[8]

Resultados de inaproximabilidad [ editar ]

Cuando $${\ displaystyle n}se refiere al tamaño del universo, Lund y Yannakakis (1994) demostraron que la cobertura del conjunto no puede aproximarse en tiempo polinómico a un factor de$${\ displaystyle {\ tfrac {1} {2}} \ log _ {2} {n} \ aprox 0.72 \ ln {n}}, a menos que NP tenga algoritmos de tiempo cuasi polinomiales . Feige (1998) mejoró este límite inferior a$${\ displaystyle {\ bigl (} 1-o (1) {\ bigr)} \ cdot \ ln {n}}bajo los mismos supuestos, que esencialmente coinciden con la relación de aproximación lograda por el algoritmo codicioso. Raz y Safra (1997) establecieron un límite inferior de$${\ displaystyle c \ cdot \ ln {n}}, dónde $${\ displaystyle c}es una cierta constante, bajo el supuesto más débil de que P$${\ displaystyle \ not =}NP . Un resultado similar con un mayor valor de$${\ displaystyle c}fue probado recientemente por Alon, Moshkovitz y Safra (2006) . Dinur y Steurer (2013) mostraron una aproximación óptima al demostrar que no puede aproximarse a$${\ displaystyle {\ bigl (} 1-o (1) {\ bigr)} \ cdot \ ln {n}}a menos que P$${\ displaystyle =}NP .

Cubierta del conjunto ponderado [ editar ]

Esta sección necesita expansión . Puedes ayudar agregándole . ( Noviembre de 2017 )

Relajando el programa lineal entero para la cobertura del conjunto ponderado indicado anteriormente , se puede usar el redondeo aleatorio para obtener un$${\ displaystyle O (\ log n)}-aproximación de factores. El análisis correspondiente para la cobertura del conjunto no ponderado se describe en Redondeo aleatorio # Algoritmo de redondeo aleatorio para la cobertura del conjunto y se puede adaptar al caso ponderado.

En la teoría de la complejidad computacional , el problema de la división de conjuntos es el siguiente problema de decisión : dada una familia F de subconjuntos de un conjunto finito S , decida si existe una partición de S en dos subconjuntos S ₁ , S _{2 de} modo que todos los elementos de F sean dividido por esta partición, es decir, ninguno de los elementos de F está completamente en S ₁ o S ₂ . Set Splitting es uno de los problemas clásicos de NP completos de Garey & Johnson . ^[1]

Variantes [ editar ]

La versión optimización de este problema se llama Max Set Splitting y requiere encontrar la partición que maximiza el número de elementos de división de F . Es un problema APX-complete ^[2] y, por lo tanto, en NPO .

El problema Set k -Splitting se establece como sigue: dado S , F y un entero k , ¿existe una partición de S que divide al menos k subconjuntos de F ? La formulación original es el caso restringido con k igual a la cardinalidad de F . El Set k -Splitting es manejable con parámetros fijos , es decir, si k se considera un parámetro fijo, en lugar de una parte de la entrada, entonces existe un algoritmo polinómico para cualquier k fijo. Dehne, Fellows y Rosamond presentaron un algoritmo que lo resuelve a tiempo$${\ displaystyle O (f (k) n ^ {c})} para alguna función f y constante c . ^[3]

Cuando cada elemento de F está restringido para ser de cardinalidad exactamente k , la variante de decisión se llama E k -Set Splitting y la versión de optimización Max E k -Set Splitting . Para k > 2, el primero permanece NP completo, y para k ≥ 2, el último permanece APX completo. ^[4] Para k ≥ 4, E k -Set Splitting es resistente a la aproximación. Es decir, a menos que P = NP, no existe un algoritmo de aproximación de tiempo polinomial (factor) que funcione esencialmente mejor que una partición aleatoria. ^[5] [6]

La división de conjunto ponderado es una variante en la que los subconjuntos en F tienen pesos y el objetivo es maximizar el peso total de los subconjuntos divididos.

Conexión a otros problemas [ editar ]

La división de conjuntos es un caso especial del problema de satisfacción no todo igual sin variables negadas. Además, E k -Set Splitting es igual a la coloración gráfica no monocromática de las hipergrafías k- uniformes . Para k = 2, la variante de optimización se reduce al conocido corte máximo .

En informática , el costo mínimo de enrutamiento que abarca el árbol de un gráfico ponderado es un árbol de expansión que minimiza la suma de las distancias por pares entre los vértices del árbol. También se conoce como la distancia óptima árbol de expansión , más corta longitud de la trayectoria total del árbol que abarca , la distancia mínima total del árbol de expansión , o árbol de expansión mínima distancia media . En un gráfico no ponderado, este es el árbol de expansión del índice Wiener mínimo . ^[1] Hu (1974) escribe que el problema de construir estos árboles fue propuesto por Francesco Maffioli. ^[2]

Es NP-difícil de construir, incluso para gráficos no ponderados. ^[3] [4] Sin embargo, tiene un esquema de aproximación de tiempo polinomial . La aproximación funciona eligiendo un número$${\ displaystyle k} eso depende de la relación de aproximación pero no del número de vértices del gráfico de entrada, y buscando entre todos los árboles con $${\ displaystyle k}nodos internos ^[5]

El costo mínimo de enrutamiento que abarca el árbol de un gráfico de intervalo no ponderado se puede construir en tiempo lineal. ^[6] También se conoce un algoritmo de tiempo polinomial para gráficos hereditarios de distancia , ponderados para que las distancias ponderadas sean hereditarias.