Set packing

Empaquetamiento de conjuntos es un problema clásico NP-completo en Teoría de la complejidad computacional y combinatoria, y fue uno de los 21 problemas de planteados por Karp.

Supongamos que tenemos un conjunto finito S y una lista de subconjuntos de S. Entonces, el problema de empaquetamiento de conjuntos pregunta si algunos de los k subconjuntos en la lista son conjuntos disjuntos (en otras palabras, ninguno de ellos tiene un elemento en común).

Más formalmente, dado un universo ${\mathcal {U}}$ y una familia ${\mathcal {S}}$ de subconjuntos de ${\mathcal {U}}$ , un empaquetamiento es una subfamilia ${\mathcal {C}}\subseteq {\mathcal {S}}$ de conjuntos tal que todos los conjuntos en ${\mathcal {C}}$ son disjuntos 2 a 2, y el tamaño del empaquetamiento es $|{\mathcal {C}}|$ . En el problema de decisión de empaquetemiento de conjuntos, la entrada es un par $({\mathcal {U}},{\mathcal {S}})$ y un entero $k$ ; la pregunta es si existe un empaquetamiento de conjuntos de tamaño mayor o igual que $k$ . En el empaquetamiento de conjuntos problema de optimización, la entrada es un par $({\mathcal {U}},{\mathcal {S}})$ , y la tarea es encontrar un empaquetamiento de conjuntos que use la mayor cantidad de conjuntos.

El problema es claramente un problema NP debido a que, dadok subconjuntos, podemos fácilmente verificar que ellos son disjuntos 2 a 2 en tiempo polinomial.

La versión del problema como problema de optimización, máximo empaquetamiento de conjuntos, pregunta por el máximo número de conjuntos disjuntos 2 a 2 en la lista. Es un problema de maximización que puede ser formulado naturalmente como un problema de programación lineal,perteneciendo a la clase de los problemas de empaquetamiento, y su problema dual linear es el problema de cubrimiento de conjuntos.^[1]

Formulación del programa de programación lineal en enteros

El problema de empaquetamiento máximo de conjuntos puede ser formulado como sigue integer linear program.

maximizar	$\sum _{S\in {\mathcal {S}}}x_{S}$		(maximizar el número total de subconjuntos)
sujeto a	$\sum _{S\colon e\in S}x_{S}\leqslant 1$	para todo $e\in {\mathcal {U}}$	(seleccionar los conjuntos que tienen que se disjuntos 2 a 2)
	$x_{S}\in \{0,1\}$	para todo $S\in {\mathcal {S}}$ .	(todo conjunto está o no en el empaquetamiento)

Ejemplos

Como un ejemplo simple, supongamos que en su cocina tiene una colección de distintos ingredienes para cocinar ( ${\mathcal {U}}$ ), y usted tiene un recetario con distintas recetas ( ${\mathcal {S}}$ ). Cada receta necesita un subconjunto de ingredientes. Usted quiere preparar el conjunto más grande de recetas que aparecen en el recetario y que necesitan de los ingredientes de los que dispone. Usted está, en resumen, buscando un empaquetamiento de conjuntos ( ${\mathcal {C}}$ ) en ( ${\mathcal {U}},{\mathcal {S}}$ ) - una colección de recetas cuyo conjunto de ingredientes son distintos 2 a 2.

Como otro ejemplo, supongamos que usted está en una convención de embajadores foráneos, cada uno de los cuales habla inglés y también otros idiomas. Usted quiere hacer un anuncio a un grupo de ellos, pero debido a que usted no confía en ellos, usted no quiere que ellos hablen entre ellos sin que usted los entienda. Para asegurar esto, usted necesitará escoger un grupo de embajadores tal que no haya 2 embajadores que hablen el mismo idioma, que no sea inglés. Por otra parte, usted también quiere entregar su anuncio a tantos embajadores como sea posible. En este caso, los elementos del conjunto son idiomas distintos del inglés, y los subconjuntos son los conjuntos de idiomas hablados por un embajador en particular. Si 2 conjuntos son disjuntos, entonces los embajadores correspondientes no comparten idiomas que no sean el inglés. Un empaquetamiento máximo escogerá el número más grande posible de embajadores bajo la restricción deseada. Aunque el problema es difícil de resolver en general, en este ejemplo una buena heurística es escoger a embajadores que solo hablen lenguajes no tan comunes primero, con el fin de que muchos otros no queden descalificados.

Versión utilizando pesos

Existe una versión con pesos del problema de empaquetamiento de conjuntos en la cual a cada subconjunto se le asocia un peso que es un número real y es este peso el que deseamos maximizar: $\sum _{S\in {\mathcal {S}}}w(S)\cdot x_{S}$

En nuestro ejemplo simple arriba, nosotros desearíamos clasificar las recetas de cocina atendiendo al número de amigos al que le gustó el plato generado por la receta, con el fin de que nuestra comida satisfaga al mayor número de amigos.

Esto parece hacer que el problema sea difícil, pero la mayoría de los resultados que se aplican al problema sin tomar en cuenta los pesos se pueden aplicar al problema con pesos también.

Heurísticas

El problema de empaquetamiento de conjuntos puede resultar difícil para algún k, pero no es difícil encontrar un k para el cual el problema es fácil con una entrada en particular. Por ejemplo, podemos usar un algoritmo greedy donde busquemos el conjunto que se interseque con el menor número de conjuntos restantes, adiciónese este conjunto a nuestra solución, y quítense los conjuntos con los cuales comparte elementos. Continuaremos haciendo esto hasta que no quede ningún conjunto por revisar, y tengamos un empaquetamiento de conjuntos de algún tamaño, aunque esto no garantiza obtener un empaquetamiento de conjuntos máximo. Aunque ningún algoritmo puede siempre dar resultados cerca del máximo (ver la sección que sigue), para muchas entradas en la práctica el algoritmo funciona bien.

Complejidad

El conjunto de problemas de empaquetamiento no es solo NP-completo, sino que su versión como problema de optimización se ha demostrado que es tan difícil como aproximar el problema del clique máximo; en particular, no puede ser aproximado dentro de ningún factor constante.^[2] El mejor algoritmo conocido hasta ahora lo aproxima en un factor de $O({\sqrt {|U|}})$ .

Sin embargo, el problema tiene una variante que es mucho más tratable: si asumimos que ningún subconjunto tiene k≥3 elementos, La respuesta puede ser aproximada dentro de un factor de k/2 + ε para todo ε > 0; en particular, el problema con conjuntos de tamaño 3 puede ser aproximado alrededor del 50 %. En otra variante más tratable, si ningún elemento ocurre en más de k de los subconjuntos, la respuesta puede ser aproximada dentro de un factor de k. Esto se cumple también para la versión con pesos.

Problemas equivalentes

Existe una reducción uno a uno en tiempo polinomial entre el problema conjunto independiente y el problema de empaquetamiento de conjuntos:

Dado un problema de empaquetamiento de conjuntos sobre una colección ${\mathcal {S}}$ , crear un grafo donde para cada conjunto $S\in {\mathcal {S}}$ hay un vértice $v_{S}$ , y hay una arista entre $v_{S}$ y $v_{T}$ ssi $S\cap T\neq \phi$ . Ahora todo conjunto independiente de vértices en el grafo generado corresponde a un empaquetamiento de conjuntos en ${\mathcal {S}}$ .
Dado un problema de independencia de conjuntos sobre un grafo $G(V,E)$ , crear una colección de conjuntos donde para cada vértice haya un conjunto conteniendo todas las aristas adyacentes a $v$ . Ahora todo empaquetamiento de conjuntos en la colección generada corresponde a un vértice independiente en $G(V,E)$ .

Esta es una aplicación bidireccional, y muestra que los 2 problemas son igualmente difíciles de aproximar.

Casos especiales

Matching y 3-dimensional matching son casos especiales de problemas de empaquetamiento de vértices. Un emparejamiento máximo puede ser encontrado en tiempo polinomial, pero encontrar el emparejamiento 3-dimensional más grande o el conjunto independiente más grande es un problema NP-duro.

Otros problemas relacionados

El empaquetamiento de conjuntos es uno dentro de la familia de problemas relacionados con el cubrimiento o particionamiento de elementos de un conjunto. Un problema estrechamente relacionado es el problema de cubrimiento de un conjunto. Aquí, también se nos da un conjunto S y una lista de conjuntos, pero el objetivo es determinar si podemos escoger k conjuntos que juntos contengan a cada elemento de S. Estos conjuntos pueden solaparse. La versión de optimización encuentra el mínimo número de tales conjuntos. El empaquetamiento máximo no necesita cubrir a cada elemento posible.

El problema NP-completo cubrimiento exacto, por otra parte, requiere que cada elemento este contenido en exactamente uno de los subconjuntos. Encontrar tal cubrimiento exacto, sin importar el tamaño, es un problema NP-completo. Sin embargo, si creamos un conjunto singleton para cada elemento de S y los adicionamos a la lista, el problema resultante es tan fácil como el problema de empaquetamiento de conjuntos.

Karp originalmente mostró que el problema del empaquetamiento de conjuntos era NP-completo a través de una reducción basada en el problema del clique.

Ver también: Empaquetamiento en hipergrafos.

Notas

↑ Vazirani (2001)
↑ Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), «On the complexity of approximating k-set packing», Computational Complexity 15 (1): 20-39, MR 2226068, doi:10.1007/s00037-006-0205-6 .. See in particular p. 21: "Maximum clique (and therefore also maximum independent set and maximum set packing) cannot be approximated to within $O(n^{1-\epsilon })$ unless NP ⊂ ZPP."

Referencias

Maximum Set Packing, Viggo Kann.
"set packing". Dictionary of Algorithms and Data Structures, editor Paul E. Black, National Institute of Standards and Technology. Note that the definition here is somewhat different.
Steven S. Skiena. "Set Packing". The Algorithm Design Manual. Last modified June 2, 1997.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. "Maximum Set Packing". A compendium of NP optimization problems. Last modified March 20, 2000.
Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A3.1: SP3, pg.221.
Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8.

Enlaces externos

[1]: A Pascal program for solving the problem. From Discrete Optimization Algorithms with Pascal Programs by MacIej M. Syslo, ISBN 0-13-215509-5.
Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination Archivado el 25 de julio de 2017 en Wayback Machine.
Solving packaging problem in PHP

Datos: Q475603

[1] Vazirani (2001)

[2] Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), «On the complexity of approximating k-set packing», Computational Complexity 15 (1): 20-39, MR 2226068, doi:10.1007/s00037-006-0205-6 .. See in particular p. 21: "Maximum clique (and therefore also maximum independent set and maximum set packing) cannot be approximated to within $O(n^{1-\epsilon })$ unless NP ⊂ ZPP."

[1]

[2]