Embalaje del conjunto

El empaquetamiento de conjuntos es un problema NP-completo clásico en la teoría de la complejidad computacional y la combinatoria , y fue uno de los 21 problemas NP-completos de Karp . Supongamos que tenemos un conjunto finito S y una lista de subconjuntos de S. Entonces, el problema del empaquetamiento de conjuntos pregunta si algunos k subconjuntos de la lista son disjuntos dos a dos (es decir, que no comparten ningún elemento).

Más formalmente, dado un universo ${\mathcal {U}}$ y una familia ${\mathcal {S}}$ de subconjuntos de ${\mathcal {U}}$ , un empaque es una subfamilia ${\mathcal {C}}\subseteq {\mathcal {S}}$ de conjuntos tales que todos los conjuntos en ${\mathcal {C}}$ son disjuntos por pares. El tamaño del empaquetamiento es $|{\mathcal {C}}|$ En el problema de decisión de empaquetamiento de conjuntos , la entrada es un par $({\mathcal {U}},{\mathcal {S}})$ y un número entero $t$ ; la pregunta es si existe un empaquetado fijo de tamaño $t$ o más. En el problema de optimización de empaquetamiento de conjuntos , la entrada es un par $({\mathcal {U}},{\mathcal {S}})$ y la tarea consiste en encontrar un empaquetamiento de conjuntos que utilice la mayor cantidad de conjuntos.

El problema está claramente en NP ya que, dado $t$ subconjuntos, podemos verificar fácilmente que son disjuntos por pares en tiempo polinomial .

La versión de optimización del problema, denominada empaquetamiento máximo de conjuntos , pide el número máximo de conjuntos disjuntos por pares en la lista. Es un problema de maximización que puede formularse de forma natural como un programa lineal entero , perteneciente a la clase de problemas de empaquetamiento .

Formulación de programación lineal entera

El problema del empaquetamiento máximo de conjuntos se puede formular como el siguiente programa lineal entero .

Complejidad

El problema de empaquetamiento de conjuntos no solo es NP-completo, sino que su versión de optimización (problema general de empaquetamiento máximo de conjuntos) ha demostrado ser tan difícil de aproximar como el problema de clique máximo ; en particular, no se puede aproximar dentro de ningún factor constante. ^{[ 1 ]} El mejor algoritmo conocido lo aproxima dentro de un factor de $O({\sqrt {|{\mathcal {U}}|}})$ . ^{[ 2 ]} La variante ponderada también puede aproximarse. ^{[ 3 ]}

Juegos de embalaje con un tamaño limitado

El problema tiene una variante más manejable. Dado cualquier entero positivo k ≥ 3, el problema de empaquetamiento de k conjuntos es una variante del problema de empaquetamiento de conjuntos en la que cada conjunto contiene como máximo k elementos.

Cuando k = 1, el problema es trivial. Cuando k = 2, el problema es equivalente a encontrar una cardinalidad máxima que coincida con , lo cual se puede resolver en tiempo polinomial.

Para cualquier k ≥3, el problema es NP-difícil, ya que es más general que el emparejamiento tridimensional . Sin embargo, existen algoritmos de aproximación con factor constante :

Cygan ^{[ 4 ]} presentó un algoritmo que, para cualquier ε>0, alcanza una aproximación de ( k +1+ε)/3. El tiempo de ejecución es polinomial en el número de conjuntos y elementos, pero doblemente exponencial en 1/ε.
Furer y Yu ^{[ 5 ]} presentaron un algoritmo que alcanza la misma aproximación, pero con un tiempo de ejecución exponencial simple en 1/ε.

Conjuntos de embalaje con un grado limitado

En otra variante más manejable, si ningún elemento aparece en más de d subconjuntos, la respuesta se puede aproximar con un factor de d . Esto también es válido para la versión ponderada.

Problemas relacionados

Problemas equivalentes

La correspondencia de hipergrafos es equivalente al empaquetamiento de conjuntos: los conjuntos se corresponden con las hiperaristas.

El problema del conjunto independiente también es equivalente al problema del empaquetamiento de conjuntos; existe una reducción biunívoca en tiempo polinomial entre ellos:

Dado un problema de empaquetamiento de conjuntos en una colección ${\mathcal {S}}$ , construir un gráfico donde para cada conjunto $S\in {\mathcal {S}}$ hay un vértice $v_{S}$ y hay un borde entre $v_{S}$ y $v_{T}$ si y solo si $S\cap T\neq \varnothing$ Cada conjunto independiente de vértices en el grafo generado corresponde a un empaquetamiento de conjuntos en ${\mathcal {S}}$ .
Dado un problema de conjunto de vértices independientes en un grafo $G(V,E)$ , construir una colección de conjuntos donde para cada vértice $v$ hay un conjunto $S_{v}$ que contiene todos los bordes adyacentes a $v$ Cada empaquetamiento de conjuntos en la colección generada corresponde a un conjunto de vértices independiente en $G(V,E)$ .

Esta es también una reducción PTAS bidireccional , y demuestra que ambos problemas son igualmente difíciles de aproximar.

En el caso especial en que cada conjunto contiene como máximo k elementos (el problema de empaquetamiento de k conjuntos ), el grafo de intersección es ( k +1) -libre de garras . Esto se debe a que, si un conjunto interseca a k +1 conjuntos, entonces al menos dos de estos conjuntos se intersecan, por lo que no puede haber una ( k +1)-garra. Por lo tanto, el Conjunto Independiente Máximo en grafos libres de garras ^{[ 6 ]} puede considerarse una generalización del Empaquetamiento Máximo de k Conjuntos.

Casos especiales

El emparejamiento de grafos es un caso especial de empaquetamiento de conjuntos en el que el tamaño de todos los conjuntos es 2 (los conjuntos corresponden a las aristas). En este caso especial, se puede encontrar un emparejamiento de tamaño máximo en tiempo polinomial.

El emparejamiento tridimensional es un caso especial en el que el tamaño de todos los conjuntos es 3, y además, los elementos se dividen en 3 colores y cada conjunto contiene exactamente un elemento de cada color. Este caso especial sigue siendo NP-difícil, aunque cuenta con mejores algoritmos de aproximación con factor constante que el caso general.

Otros problemas relacionados

En el problema de cobertura de conjuntos , se nos da una familia ${\mathcal {S}}$ de subconjuntos de un universo ${\mathcal {U}}$ y el objetivo es determinar si podemos elegir t conjuntos que juntos contengan cada elemento de ${\mathcal {U}}$ Estos conjuntos pueden superponerse. La versión de optimización encuentra el número mínimo de dichos conjuntos. El empaquetamiento máximo de conjuntos no tiene por qué abarcar todos los elementos posibles.

En el problema exacto de la cobertura , cada elemento de ${\mathcal {U}}$ Debe estar contenido en exactamente uno de los subconjuntos. Encontrar una cobertura exacta de este tipo es un problema NP-completo , incluso en el caso especial en que el tamaño de todos los conjuntos es 3 (este caso especial se denomina cobertura exacta de 3 o X3C ). Sin embargo, si creamos un conjunto unitario para cada elemento de S y los añadimos a la lista, el problema resultante es tan sencillo como el empaquetamiento de conjuntos.

Karp demostró originalmente que el empaquetamiento de conjuntos es NP-completo mediante una reducción del problema de la camarilla .

Notas

↑ Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), "Sobre la complejidad de la aproximación del empaquetamiento de k conjuntos", Computational Complexity , 15 (1): 20–39 , CiteSeerX 10.1.1.352.5754 , doi : 10.1007/s00037-006-0205-6 , MR 2226068 , S2CID 1858087 . Véase en particular la pág. 21: "La camarilla máxima (y por lo tanto también el conjunto independiente máximo y el empaquetamiento de conjuntos máximo) no se puede aproximar dentro de $O(n^{1-\epsilon })$ a menos que NP ⊂ ZPP."
↑ Halldórsson, Magnus M.; Kratochvíl, Jan; Telle, Jan Arne (1998). Conjuntos independientes con restricciones de dominación . XXV Coloquio Internacional sobre Autómatas, Lenguajes y Programación. Lecture Notes in Computer Science. Vol. 1443. Springer-Verlag. pp. 176–185 .
↑ Halldórsson, Magnus M. (1999). Aproximaciones de problemas de conjuntos independientes ponderados y subconjuntos hereditarios . 5.ª Conferencia Internacional Anual sobre Computación y Combinatoria. Lecture Notes in Computer Science. Vol. 1627. Springer-Verlag. pp. 261–270 .
↑ Cygan, Marek (octubre de 2013). "Aproximación mejorada para la correspondencia tridimensional mediante búsqueda local de ancho de ruta limitado". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . pp. 509–518 . arXiv : 1304.1424 . doi : 10.1109/FOCS.2013.61 . ISBN 978-0-7695-5135-7. S2CID 14160646 .
↑ Fürer, Martin; Yu, Huiwen (2014). "Aproximación del problema de empaquetamiento $de k$ conjuntos mediante mejoras locales" . En Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T. (eds.). Optimización combinatoria . Lecture Notes in Computer Science. Vol. 8596. Cham: Springer International Publishing. pp. 408–420 . doi : 10.1007/978-3-319-09174-7_35 . ISBN 978-3-319-09174-7. S2CID 15815885 .
↑ Neuwohner, Meike (2021). "Un algoritmo de aproximación mejorado para el problema de conjunto independiente de peso máximo en gráficos libres $de d$ -garra". En Bläser, Markus; Monmege, Benjamín (eds.). 38.º Simposio internacional sobre aspectos teóricos de la informática, STACS 2021, 16 al 19 de marzo de 2021, Saarbrücken, Alemania (conferencia virtual) . LÍPICOS. vol. 187. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 53:1–53:20. arXiv : 2106.03545 . doi : 10.4230/LIPICS.STACS.2021.53 .

Referencias

« Empaquetamiento de conjuntos ». Diccionario de algoritmos y estructuras de datos , editor Paul E. Black, Instituto Nacional de Estándares y Tecnología. Cabe señalar que la definición aquí es algo diferente.
Steven S. Skiena. " Empaquetamiento de conjuntos ". El manual de diseño de algoritmos .
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski y Gerhard Woeginger . " Empaquetamiento máximo de conjuntos ". Un compendio de problemas de optimización NP . Última modificación: 20 de marzo de 2000.
Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . WH Freeman. ISBN 978-0-7167-1045-5.A3.1: SP3, pág. 221.
Vazirani, Vijay V. (2001). Algoritmos de aproximación . Springer-Verlag. ISBN 978-3-540-65367-7.

Enlaces externos

: Un programa en Pascal para resolver el problema. De Algoritmos de optimización discreta con programas en Pascal por MacIej M. Syslo, ISBN 0-13-215509-5.
Puntos de referencia con soluciones óptimas ocultas para la cobertura de conjuntos, el empaquetamiento de conjuntos y la determinación del ganador. Archivado el 25/07/2017 en Wayback Machine.
Solución del problema de empaquetado en PHP
Optimización del empaquetado tridimensional de contenedores

[1] Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), "Sobre la complejidad de la aproximación del empaquetamiento de k conjuntos", Computational Complexity , 15 (1): 20–39 , CiteSeerX 10.1.1.352.5754 , doi : 10.1007/s00037-006-0205-6 , MR 2226068 , S2CID 1858087 . Véase en particular la pág. 21: "La camarilla máxima (y por lo tanto también el conjunto independiente máximo y el empaquetamiento de conjuntos máximo) no se puede aproximar dentro de $O(n^{1-\epsilon })$ a menos que NP ⊂ ZPP."

[2] Halldórsson, Magnus M.; Kratochvíl, Jan; Telle, Jan Arne (1998). Conjuntos independientes con restricciones de dominación . XXV Coloquio Internacional sobre Autómatas, Lenguajes y Programación. Lecture Notes in Computer Science. Vol. 1443. Springer-Verlag. pp. 176–185 .

[3] Halldórsson, Magnus M. (1999). Aproximaciones de problemas de conjuntos independientes ponderados y subconjuntos hereditarios . 5.ª Conferencia Internacional Anual sobre Computación y Combinatoria. Lecture Notes in Computer Science. Vol. 1627. Springer-Verlag. pp. 261–270 .

[4] Cygan, Marek (octubre de 2013). "Aproximación mejorada para la correspondencia tridimensional mediante búsqueda local de ancho de ruta limitado". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . pp. 509–518 . arXiv : 1304.1424 . doi : 10.1109/FOCS.2013.61 . ISBN 978-0-7695-5135-7. S2CID 14160646 .

[5] Fürer, Martin; Yu, Huiwen (2014). "Aproximación del problema de empaquetamiento $de k$ conjuntos mediante mejoras locales" . En Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T. (eds.). Optimización combinatoria . Lecture Notes in Computer Science. Vol. 8596. Cham: Springer International Publishing. pp. 408–420 . doi : 10.1007/978-3-319-09174-7_35 . ISBN 978-3-319-09174-7. S2CID 15815885 .

[6] Neuwohner, Meike (2021). "Un algoritmo de aproximación mejorado para el problema de conjunto independiente de peso máximo en gráficos libres $de d$ -garra". En Bläser, Markus; Monmege, Benjamín (eds.). 38.º Simposio internacional sobre aspectos teóricos de la informática, STACS 2021, 16 al 19 de marzo de 2021, Saarbrücken, Alemania (conferencia virtual) . LÍPICOS. vol. 187. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 53:1–53:20. arXiv : 2106.03545 . doi : 10.4230/LIPICS.STACS.2021.53 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]