# Empacotamento de conjuntos

Empacotamento de conjuntos é um clássico NP-completo problema em complexidade computacional teoria e análise combinatória, e foi um dos Karp 21 problemas NP-completos.
Suponha que temos um conjunto finito S e uma lista de subconjuntos de S. Então, problema de empacotamento de conjuntos pergunta se algum conjunto com k subconjuntos da lista são dois a dois disjuntos (em outras palavras, não há dois compartilham um elemento).
Mais formalmente, dado um universo ${\mathcal {U}}$ e uma família ${\mathcal {S}}$ de subconjuntos de ${\mathcal {U}}$, um empacotamento é uma subfamília ${\mathcal {C}}\subseteq {\mathcal {S}}$ de conjuntos de tal forma que todos os conjuntos em ${\mathcal {C}}$ são disjuntos dois a dois, e o tamanho do pacote é $|{\mathcal {C}}|$. No problema de decisão de empacotamento de conjuntos, a entrada é um par $({\mathcal {U}},{\mathcal {S}})$ e um inteiro $k$; a questão é se há um pacote de conjuntos de tamanho $k$ ou mais. No problema de otimização de empacotamento de conjuntos, a entrada é o par $({\mathcal {U}},{\mathcal {S}})$, e a tarefa é encontrar um pacote de conjuntos que utilize a maioria dos conjuntos.
O problema está, claramente, em NP, uma vez que, dado k subconjuntos, podemos facilmente verificar que eles são pares disjuntos em tempo polinomial.
A versão otimizada do problema, o máximo empacotamento de conjuntos, pede-lhe o número máximo de pares disjuntos conjuntos na lista. É um problema de maximização, que pode ser formulado, naturalmente, como um programa linear inteiro, pertence à classe de problemas de empacotamento, e o seu dual programa linear é o problema da cobertura de conjuntos.

## Formulação do programa linear inteiro

O conjunto máximo de embalagem problema pode ser formulado como o seguinte programa linear inteiro.
| maximizar | $\sum _{S\in {\mathcal {S}}}x_{S}$ | | (maximizar o número total de subconjuntos) |
| sujeito a | $\sum _{S\colon e\in S}x_{S}\leqslant 1$ | para todo $e\in {\mathcal {U}}$ | (conjuntos selecionados tem que ser par disjunto) |
| | $x_{S}\in \{0,1\}$ | para todo $S\in {\mathcal {S}}$. | (cada conjunto é o pacote de conjuntos ou não) |

## Exemplos

Como um exemplo simples, suponha que a sua cozinha contém uma coleção de diferentes ingredientes de alimentos ($$), e você tem um livro de receitas com uma coleção de receitas ( $$). Cada receita exige um subconjunto dos ingredientes. Você pretende preparar a maior coleção de receitas do livro. Na verdade, você está procurando por um empacotamento ($$) no ($$) - uma coleção de receitas cujos conjuntos de ingredientes são pares disjuntos.
Como outro exemplo, suponha que você esteja em uma convenção de embaixadores estrangeiros, cada um dos quais fala inglês e várias outras línguas. Você deseja fazer um anúncio a um grupo deles, mas por você não confiar neles, você não quer que eles sejam capazes de conversar entre si sem que você seja capaz de compreendê-los. Para garantir isso, você vai escolher um grupo de tal forma que não há dois embaixadores que falem a mesma língua, que não o inglês. Por outro lado, você também quer dar o seu anúncio como embaixadores possível. Neste caso, os elementos do conjunto são outros idiomas que não o inglês, e os subconjuntos são os conjuntos de línguas faladas por um determinado embaixador. Se dois conjuntos são disjuntos, os dois embaixadores compartilham outros idiomas que não o inglês. Um conjunto máximo de empacotamento irá escolher o maior número possível de embaixadores, sob a pretendida restrição. Embora este problema é de difícil resolução e, em geral, neste exemplo, uma boa heurística é escolher primeiro embaixadores que só falam línguas incomuns, de modo que muitas pessoas são desqualificados.

## Versão ponderada

Há uma versão ponderada do problema do empacotamento de conjunto em que cada subconjunto é atribuído um peso real e é esse peso que deseja maximizar: $$
No nosso simples exemplo acima, podemos peso das receitas de acordo com o número de amigos que amam a resultante pratos, para que o nosso jantar vai agradar o maior número de amigos.

## Heurísticas

O problema de empacotamento de conjuntos que pode ser difícil para alguns k, mas não é difícil encontrar um k para o qual é fácil em uma determinada entrada. Por exemplo, podemos utilizar um algoritmo guloso onde olhamos para o conjunto que cruza o menor número de outros conjuntos, adicioná-lo para a nossa solução, e remover os conjuntos intersectados. Estamos continuamente fazendo isso até que não tenham conjuntos restantes, e temos um pacote de conjuntos do tamanho de alguns, apesar de não ser o máximo empacotamento de conjuntos. Embora nenhum algoritmo possa sempre produzir resultados perto do máximo (veja a próxima seção).

## Complexidade

O problema de empacotamento de conjuntos não é apenas um problema NP-completo, mas a sua versão otimizada (problema do máximo empacotamento de conjuntos) tem sido comprovada de tão difícil aproximação quanto como o problema do máximo clique; em particular, ele não pode ser aproximado dentro de qualquer fator constante. O melhor algoritmo conhecido aproxima dentro de um factor de $$. A versão ponderada também pode ser aproximada assim.
No entanto, o problema tem uma variante que é mais tratável: se nós não assumimos nenhuma subconjunto excede k≥3 elementos, a resposta pode ser aproximada dentro de um fator de k/2 + ε para qualquer ε > 0; em particular, o problema com 3 conjuntos de elementos pode ser estimado em cerca de 50%. Em outra variante mais tratável, se nenhum elemento ocorre em mais de k de subconjuntos, a resposta pode ser aproximada dentro de um fator de k. Isso também é verdadeiro para o versão ponderada.

## Problemas equivalentes

Existe uma redução de tempo polinomial de um-para-um entre o problema do conjunto independente e o problema de empacotamento de conjuntos:
* Dado o problema de empacotamento de conjuntos sobre uma coleção ${\mathcal {S}}$, crie um grafo onde para cada conjunto $S\in {\mathcal {S}}$ existe um vértice $v_{S}$, e existe uma aresta entre $v_{S}$ e $v_{T}$ sse $S\cap T\neq \phi$. Agora, cada conjunto independente de vértices no grafo gerado corresponde à um pacote de conjuntos em ${\mathcal {S}}$.
* Dado um problema de conjuntos de vértices independentes em um grafo $G(V,E)$, crie uma coleção de conjuntos onde para cada vértice $v$ existe um conjunto $S_{v}$ contendo todos os vértices adjacentes à $v$. Agora, cada pacote de conjuntos na coleção gerada corresponde à um conjunto de vértices independentes em $G(V,E)$.
Este é também um bidirecional redução APMS, e mostra que os dois problemas são igualmente difíceis para se aproximar.

## Casos especiais

Correspondência e 3-dimensional de correspondência são casos especiais de de empacotamento. Uma correspondente de tamanho máximo pode ser encontrada em tempo polinomial, mas encontrar um maior 3-dimensional de correspondência ou de um maior conjunto independente é NP-difícil.

## Outros problemas relacionados

Definir o empacotamento é uma entre uma família de problemas relacionados à cobertura ou particionamento de elementos de um conjunto. Um problema intimamente relacionado é o problema de cobertura de conjuntos. Aqui, também dado um conjunto S e uma lista de conjuntos, mas o objetivo é determinar se podemos escolher k conjuntos que, juntos, contêm todos os elementos de S. Estes conjuntos podem sobrepor-se. A versão otimizada encontra, o número mínimo de tais conjuntos. O conjunto máximo de empacotament não precisa cobrir todos os possíveis elementos.
O problema NP-completo da cobertura exata, por outro lado, exige que cada elemento a ser contidos em exatamente um dos subconjuntos. Encontrar uma cobertura exata em tudo, independentemente do tamanho, é um problema NP-completo. No entanto, se criar um conjunto singleton para cada elemento de S e adicioná-las à lista, o problema resultante é tão fácil como o empacotamento de conjuntos.
Karp originalmente mostrou que empacotamento de conjuntos é NP-completo através de uma redução da camarilha problema.
Veja também: Packing in a hypergraph.