Establecer embalaje

El empaquetado de conjuntos es un problema NP-completo clásico en teoría de la complejidad computacional y combinatoria , y fue uno de los 21 problemas NP-completos de Karp . Supongamos que uno tiene un conjunto finito S y una lista de subconjuntos de S. Luego, el problema de empaquetado de conjuntos pregunta si algunos k subconjuntos de la lista son disjuntos por pares (en otras palabras, no hay dos que compartan un elemento).

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

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

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

Formulación de programa lineal entero.

El problema de empaquetado de conjuntos máximos se puede formular como el siguiente programa lineal entero .

Complejidad

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

Juegos de embalaje con un tamaño acotado.

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

Cuando k =1, el problema es trivial. Cuando k = 2, el problema equivale a encontrar una coincidencia de cardinalidad máxima , que puede resolverse en tiempo polinómico.

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

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

Juegos de embalaje con grado acotado.

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

Problemas relacionados

Problemas equivalentes

La coincidencia de hipergrafos es equivalente al empaquetado de conjuntos: los conjuntos corresponden a los hiperbordes.

El problema de conjuntos independientes también es equivalente al empaquetado de conjuntos: existe una reducción de tiempo polinomial uno a uno entre ellos:

• Dado un problema de empaquetamiento de conjuntos en una colección , construya un gráfico donde para cada conjunto haya un vértice y haya una arista entre y si y así . Cada conjunto independiente de vértices en el gráfico generado corresponde a un conjunto empaquetado en . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle S\in {\mathcal {S}}}$ ${\displaystyle v_{S}}$ ${\displaystyle v_{S}}$ ${\displaystyle v_{T}}$ ${\displaystyle S\cap T\neq \varnothing }$ ${\displaystyle {\mathcal {S}}}$
• Dado un problema de conjunto de vértices independiente en un gráfico , construya una colección de conjuntos donde para cada vértice haya un conjunto que contenga todos los bordes adyacentes . Cada paquete de conjuntos en la colección generada corresponde a un vértice independiente establecido en . ${\displaystyle G(V,E)}$ ${\displaystyle v}$ ${\displaystyle S_{v}}$ ${\displaystyle v}$ ${\displaystyle G(V,E)}$

Esta también es una reducción bidireccional de PTAS y muestra que los dos problemas son igualmente difíciles de aproximar.

En el caso especial en el que cada conjunto contiene como máximo k elementos (el problema de empaquetamiento del conjunto k ), el gráfico de intersección es ( k +1)-libre de garras . Esto se debe a que, si un conjunto intersecta algunos k +1 conjuntos, entonces al menos dos de estos conjuntos se cruzan, por lo que no puede haber una garra ( k +1). Por lo tanto, el conjunto máximo independiente en gráficos sin garras ^[6] puede verse como una generalización del embalaje máximo de k -Set.

Casos especiales

La coincidencia de gráficos es un caso especial de empaquetado de conjuntos en el que el tamaño de todos los conjuntos es 2 (los conjuntos corresponden a los bordes). En este caso especial, se puede encontrar una coincidencia de tamaño máximo en tiempo polinomial.

La combinación 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-duro, aunque tiene mejores algoritmos de aproximación de factor constante que el caso general.

Otros problemas relacionados

En el problema de cobertura de conjuntos , se nos da una familia de subconjuntos de un universo , y el objetivo es determinar si podemos elegir t conjuntos que juntos contengan todos los elementos de . Estos conjuntos pueden superponerse. La versión de optimización encuentra el número mínimo de dichos conjuntos. No es necesario que el embalaje máximo del conjunto cubra todos los elementos posibles. ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {U}}}$ ${\displaystyle {\mathcal {U}}}$

En el problema de cobertura exacta , cada elemento de debe estar contenido exactamente en uno de los subconjuntos. Encontrar una cobertura tan exacta es un problema NP-completo , incluso en el caso especial en el que el tamaño de todos los conjuntos es 3 (este caso especial se llama cobertura 3 exacta o X3C ). Sin embargo, si creamos un conjunto singleton para cada elemento de S y los agregamos a la lista, el problema resultante es tan fácil como empaquetar conjuntos. ${\displaystyle {\mathcal {U}}}$

Karp originalmente mostró el empaquetado del conjunto NP-completo mediante una reducción del problema de la camarilla .

Notas

1. Hazán, Elad; Safra, Shmuel; Schwartz, Oded (2006), "Sobre la complejidad de aproximar el embalaje de k -set", Computational Complexity , 15 (1): 20–39, CiteSeerX  10.1.1.352.5754 , doi :10.1007/s00037-006-0205-6, SEÑOR  2226068, S2CID  1858087. Véase en particular la pág. 21: "La camarilla máxima (y por lo tanto también el conjunto máximo independiente y el empaquetamiento máximo del conjunto) no pueden aproximarse a menos que NP ⊂ ZPP". ${\displaystyle O(n^{1-\epsilon })}$
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. Apuntes de conferencias sobre informática. vol. 1443. Springer-Verlag. págs. 176–185.
3. Halldórsson, Magnus M. (1999). "Aproximaciones de problemas de conjuntos independientes ponderados y subconjuntos hereditarios" . V Congreso Internacional Anual de Computación y Combinatoria. Apuntes de conferencias sobre informática. vol. 1627. Springer-Verlag. págs. 261-270.
4. Cygan, Marek (octubre de 2013). "Aproximación mejorada para coincidencias tridimensionales mediante búsqueda local de ancho de ruta acotado". 2013 54º Simposio Anual del IEEE sobre Fundamentos de la Informática . págs. 509–518. arXiv : 1304.1424 . doi :10.1109/FOCS.2013.61. ISBN 978-0-7695-5135-7. S2CID  14160646.
5. Fürer, Martín; Yu, Huiwen (2014). "Aproximación del problema de embalaje del k-set mediante mejoras locales". En Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T. (eds.). Optimización combinatoria . Apuntes de conferencias sobre informática. vol. 8596. Cham: Editorial Internacional Springer. págs. 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.

Referencias

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

enlaces externos

• [1]: Un programa Pascal para resolver el problema. De Algoritmos de optimización discretos con programas Pascal de MacIej M. Syslo, ISBN 0-13-215509-5 . 
• Puntos de referencia con soluciones óptimas ocultas para cobertura de escenarios, embalaje de escenarios y determinación del ganador
• Resolviendo el problema de empaquetado en PHP
• Optimización del embalaje de contenedores tridimensionales