Set packing

Categoría:Wikipedia:Traducciones para mejorar Empaquetamiento de conjunts és un problema clàssic NP-complet en Teoria de la complexitat computacional i combinatòria, i va ser un dels 21 problemes de plantejats per Karp.

Supongam que tenim un conjunt finito S i una llista de subconjunts de S. Llavors, el problema de empaquetamiento de conjunts pregunta si alguns dels k subconjunts en la llista són conjunts disjuntos (en atres paraules, cap d'ells té un element en comú).

Més formalment, donat un univers $𝒰$ i una família $𝒮$ de subconjunts de $𝒰$, un empaquetamiento és una subfamília $𝒞\subseteq 𝒮$ de conjunts tal que tots els conjunts en $𝒞$ són disjuntos 2 a 2, i el tamany del empaquetamiento és $|𝒞|$. En el problema de decisió de empaquetemiento de conjunts, l'entrada és un parell $(𝒰,𝒮)$ i un sancer $k$; la pregunta és si existix un empaquetamiento de conjunts de tamany major o igual que $k$. En el empaquetamiento de conjunts problema d'optimisació, l'entrada és un parell $(𝒰,𝒮)$, i la tasca és trobar un empaquetamiento de conjunts que use la major cantitat de conjunts.

El problema és clarament un problema NP degut a que, donatk subconjunts, podem fàcilment verificar que ells són disjuntos 2 a 2 en temps polinomial.

La versió del problema com problema d'optimisació, màxim empaquetamiento de conjunts, pregunta pel màxim número de conjunts disjuntos 2 a 2 en la llista. És un problema d'maximización que pot ser formulat naturalment com un problema de programació llineal,pertanyent a la classe dels problemes de empaquetamiento, i el seu problema dual linear és el problema de cubrimiento de conjunts.

Formulació del programa de programació llineal en sancers

El problema de empaquetamiento màxim de conjunts pot ser formulat com seguix integer linear program.

maximizar	$\sum _{S\in 𝒮}{x}_S$		(maximizar el número total de subconjunts)
$\sum _{S:e\in S}{x}_S⩽1$	para tot $e\in 𝒰$	(seleccionar els conjunts que tenen que es disjuntos 2 a 2)
	$x_S\in \{0,1\}$	para tot $S\in 𝒮$.	(tot conjunt està o no en el empaquetamiento)

Eixemples

Com un eixemple simple, supongam que en la seua cuina té una colecció de distints ingredienes per a cuinar ($𝒰$), i vosté té un recetario en distintes receptes ($𝒮$). Cada recepta necessita un subconjunt d'ingredients. Vosté vol preparar el conjunt més gran de receptes que apareixen en el recetario i que necessiten dels ingredients dels que dispon. Vosté està, en resum, buscant un empaquetamiento de conjunts ($𝒞$) en ($𝒰,𝒮$) - una colecció de receptes el conjunt de les quals d'ingredients són distints 2 a 2.

Com un atre eixemple, supongam que vosté està en una convenció d'embaixadors foràneus, cada u dels quals parla anglés i també atres idiomes. Vosté vol fer un anunci a un grup d'ells, pero degut a que vosté no confia en ells, vosté no vol que ells parlen entre ells sense que vosté els entenga. Per a assegurar açò, vosté necessitarà triar un grup d'embaixadors tal que no hi haja 2 embaixadors que parlen el mateix idioma, que no siga anglés. Per una atra part, vosté també vol entregar el seu anunci a tants embaixadors com siga possible. En este cas, els elements del conjunt són idiomes distints de l'anglés, i els subconjunts són els conjunts d'idiomes parlats per un embaixador en particular. Si 2 conjunts són disjuntos, llavors els embaixadors corresponents no compartixen idiomes que no siguen l'anglés. Un empaquetamiento màxim triarà el número més gran possible d'embaixadors baix la restricció desijada. Encara que el problema és difícil de resoldre en general, en este eixemple una bona heurística és triar a embaixadors que solament parlen llenguages no tan comuns primer, en la finalitat de que molts uns atres no queden descalificats.

Referències

• 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.