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 (${\displaystyle }$), e você tem um livro de receitas com uma coleção de receitas ( ${\displaystyle }$). 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 (${\displaystyle }$) no (${\displaystyle }$) - 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: ${\displaystyle }$

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 ${\displaystyle }$. 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.

Referências

• 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. [S.l.]: W.H. Freeman. ISBN 0-7167-1045-5  A3.1: SP3, pg.221.
• Vazirani, Vijay V. (2001). Approximation Algorithms. [S.l.]: Springer-Verlag. ISBN 3-540-65367-8 

Ligações externas

• [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
• Solving packaging problem in PHP