El empaquetado de conjuntos es un problema NP-completo clásico en la 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 . Entonces, el problema de embalaje conjunto pregunta si algunos k subconjuntos de la lista son dos a dos disjuntos (en otras palabras, no hay dos de ellos comparten un elemento).
Más formalmente, dado un universo y una familia de subconjuntos de , un embalaje es una subfamilia de conjuntos tales que todos los conjuntos en son disjuntos por pares. El tamaño del embalaje es. En el problema de decisión de empaquetado de conjuntos , la entrada es un par y un entero ; la cuestión es si existe un embalaje de tamaño determinadoo más. En el problema de optimización de empaquetado de conjuntos , la entrada es un par, y la tarea es encontrar un paquete de conjuntos que utilice la mayor cantidad de conjuntos.
El problema está claramente en NP ya que, dados k subconjuntos, podemos verificar fácilmente que son disjuntos por pares en el tiempo polinomial .
La versión de optimización del problema, empaquetado 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 de enteros , perteneciente a la clase de problemas de empaquetamiento .
Formulación de programas lineales enteros
El problema de empaquetado de conjuntos máximos se puede formular como el siguiente programa lineal de enteros .
maximizar | (maximizar el número total de subconjuntos) | ||
sujeto a | para todos | (los conjuntos seleccionados deben estar separados por pares) | |
para todos . | (cada juego está en el paquete del juego o no) |
Complejidad
El problema del empaque del conjunto no es solo NP-completo, sino que su versión de optimización (problema general del empaque del conjunto máximo) ha demostrado ser tan difícil de aproximar como el problema de la camarilla máxima ; en particular, no se puede aproximar dentro de ningún factor constante. [1] El algoritmo más conocido lo aproxima en un factor de. [2] La variante ponderada también se puede aproximar. [3]
Sin embargo, el problema tiene una variante que es más manejable: si asumimos que ningún subconjunto excede k ≥3 elementos, la respuesta puede aproximarse dentro de un factor de k / 2 + ε para cualquier ε> 0; en particular, el problema con los conjuntos de 3 elementos se puede aproximar en aproximadamente el 50%. En otra variante más manejable, si ningún elemento ocurre en más de k de los subconjuntos, la respuesta puede aproximarse dentro de un factor de k . Esto también es válido para la versión ponderada.
Problemas equivalentes
Hay una reducción de tiempo polinómico uno a uno entre el problema de conjuntos independientes y el problema de empaquetado de conjuntos:
- Dado un problema de empaquetado en una colección , crea un gráfico donde para cada conjunto hay un vértice , y hay una ventaja entre y Si . Ahora, cada conjunto independiente de vértices en el gráfico generado corresponde a un conjunto de empaquetamiento en.
- Dado un problema de conjunto de vértices independiente en una gráfica , crea una colección de conjuntos donde para cada vértice hay un conjunto que contiene todos los bordes adyacentes a . Ahora cada paquete de conjuntos en la colección generada corresponde a un vértice independiente establecido en.
Esta es también una reducción de PTAS bidireccional y muestra que los dos problemas son igualmente difíciles de aproximar.
Casos especiales
El emparejamiento y el emparejamiento tridimensional son casos especiales de empaquetado. Se puede encontrar una coincidencia de tamaño máximo en tiempo polinomial, pero encontrar una coincidencia tridimensional más grande o un conjunto independiente más grande es NP-difícil.
El empaquetado de conjuntos es uno de una familia de problemas relacionados con el recubrimiento o la división de los elementos de un conjunto. Un problema estrechamente relacionado es el problema de la cobertura del set . A continuación, se nos da también un conjunto S y una lista de conjuntos, pero el objetivo es determinar si podemos elegir k conjuntos que juntos contienen todos los elementos de S . Estos conjuntos pueden superponerse. La versión de optimización encuentra el número mínimo de tales conjuntos. No es necesario que el embalaje ajustado máximo cubra todos los elementos posibles.
El problema de cobertura exacta NP-completo , por otro lado, requiere que cada elemento esté contenido exactamente en uno de los subconjuntos. Encontrar una cubierta tan exacta, independientemente del tamaño, es un problema NP-completo . 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.
Karp mostró originalmente el empaquetado NP-completo a través de una reducción del problema de la camarilla .
Consulte también: Empaquetado en un hipergráfico .
Notas
- ^ Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), "Sobre la complejidad de aproximar el empaquetado 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. Ver en particular la p. 21: "La camarilla máxima (y, por lo tanto, también el conjunto máximo independiente y el embalaje del conjunto máximo) no se pueden aproximar dentro de a menos que NP ⊂ ZPP ".
- ^ Halldórsson, Magnus M .; Kratochvíl, Jan; Telle, Jan Arne (1998). Conjuntos independientes con restricciones de dominación . 25º Coloquio Internacional sobre Autómatas, Lenguajes y Programación. Apuntes de conferencias en Ciencias de la Computación. 1443 . Springer-Verlag. págs. 176-185.
- ^ Halldórsson, Magnus M. (1999). Aproximaciones de problemas ponderados de conjuntos independientes y subconjuntos hereditarios . V Congreso Internacional Anual de Computación y Combinatoria. Apuntes de conferencias en Ciencias de la Computación. 1627 . Springer-Verlag. págs. 261-270.
Referencias
- Embalaje de juego máximo , Viggo Kann.
- " establecer 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 de conjunto máximo ". Un compendio de problemas de optimización de 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 NP-Completeness . 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 la cobertura del set, el embalaje del set y la determinación del ganador
- Resolviendo el problema de empaquetado en PHP
- Optimización del embalaje de contenedores tridimensionales