Problema de cobertura de conjuntos

O problema de cobertura de conjuntos é uma questão clássica em combinatória, ciência da computação, pesquisa operacional e teoria da complexidade computacional . É um dos 21 problemas NP-completos de Karp mostrado ser NP-completo em 1972.

É um problema "cujo estudo levou ao desenvolvimento de técnicas fundamentais para todo o campo" dos algoritmos de aproximação .

Dado um conjunto universo $\{1,2,...,n\}$ e uma coleção $S$ de $m$ conjuntos cuja união é igual ao conjunto universo, o problema de cobertura de conjunto é identificar a menor sub-coleção de $S$ cuja união é igual ao conjunto universo. Por exemplo, considere o conjunto universo $U=\{1,2,3,4,5\}$ e a coleção de conjuntos $S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}$ . Claramente a união de $S$ é $U$ . No entanto, podemos cobrir todos os elementos com o mínimo número de conjuntos a seguir : $\{\{1,2,3\},\{4,5\}\}$ .

Mais formalmente, dado um conjunto universo $U$ e uma família $S$ de subconjuntos de $U$, uma capa é uma subfamília $C\subseteq S$ de conjuntos cuja união é $U$ . No conjunto que cumpre o problema de decisão, a entrada é um par $(U,S)$ e um inteiro $k$ ; a questão é se há uma cobertura de conjuntos de tamanho $k$ ou menos. No conjunto que cumpre o problema de otimização, a entrada é um par $(U,S)$, e a tarefa é encontrar uma cobertura de conjuntos que use o menor número de conjuntos.

A versão de decisão da cobertura do conjunto é NP-completa, e a versão de otimização / busca da cobertura do conjunto é NP-difícil .

Se cada conjunto tiver um custo atribuído, ele se tornará um problema de cobertura de conjuntos ponderado .

Formulação do programa linear inteiro

O problema de cobertura mínima de conjuntos pode ser formulado como a seguinte programação inteira (PI).

minimizar	$\sum _{S\in {\mathcal {S}}}x_{S}$		(minimizar o número de conjuntos)
sujeito a	$\sum _{S\colon e\in S}x_{S}\geqslant 1$	para todos $e\in {\mathcal {U}}$	(cubra todos os elementos do universo)
	$x_{S}\in \{0,1\}$	para todos $S\in {\mathcal {S}}$ .	(cada conjunto está na capa ou não)

Essa PI pertence à classe mais geral de PIs para problemas de cobertura . A lacuna de integralidade deste PI é no máximo $\scriptstyle \log n$, então seu relaxamento dá um fator $\scriptstyle \log n$ no algoritmo de aproximação para o problema de problema de cobertura mínima de conjuntos mínimo definida (onde $\scriptstyle n$ é o tamanho do universo).

Na cobertura de conjuntos ponderados, os conjuntos recebem pesos. Denota o peso do conjunto $S\in {\mathcal {S}}$ de $w_{S}$ . Então, o programa linear inteiro que descreve a cobertura do conjunto ponderado é idêntico ao fornecido acima, exceto que a função objetivo para minimizar é $\sum _{S\in {\mathcal {S}}}w_{S}x_{S}$ .

Formulação do conjunto de acerto

A cobertura de conjuntos é equivalente ao problema do conjunto de acerto . Isso é visto ao observar que uma instância de cobertura de conjunto pode ser vista como um grafo bipartido arbitrário, com conjuntos representados por vértices à esquerda, o universo representado por vértices à direita e arestas representando a inclusão de elementos em conjuntos. A tarefa é então encontrar um subconjunto de cardinalidade mínima de vértices esquerdos que cubra todos os vértices direitos. No problema do conjunto de acertos, o objetivo é cobrir os vértices esquerdos usando um subconjunto mínimo dos vértices direitos. A conversão de um problema para o outro é, portanto, alcançada trocando os dois conjuntos de vértices.

Algoritmo guloso

Existe um algoritmo guloso para aproximação de tempo polinomial de cobertura de conjunto que escolhe conjuntos de acordo com uma regra: em cada estágio, escolha o conjunto que contém o maior número de elementos descobertos. Pode ser provado que este algoritmo atinge uma razão de aproximação de $H(s)$, Onde $s$ é o tamanho do conjunto a ser coberto. Em outras palavras, ele encontra uma cobertura que pode ser $H(n)$ vezes tão grande quanto o mínimo, onde $H(n)$ é o $n$ -ésimo número harmônico :

$H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1$

Este algoritmo guloso realmente atinge uma proporção de aproximação de $H(s^{\prime })$ Onde $s^{\prime }$ é o conjunto de cardinalidade máxima de $S$ . Para $\delta -$ instâncias densas, no entanto, existe um $c\ln {m}$ - algoritmo de aproximação para cada $c>0$ .

Exemplo resumido para o algoritmo guloso com k = 3

Há um exemplo padrão no qual o algoritmo guloso atinge uma proporção de aproximação de $\log _{2}(n)/2$ . O universo consiste em $n=2^{(k+1)}-2$ elementos O sistema definido consiste em $k$ conjuntos disjuntos em pares $S_{1},\ldots ,S_{k}$ com tamanhos $2,4,8,\ldots ,2^{k}$ respectivamente, bem como dois conjuntos adicionais separados $T_{0},T_{1}$, cada um dos quais contém metade dos elementos de cada $S_{i}$ . Nesta entrada, o algoritmo guloso pega os conjuntos $S_{k},\ldots ,S_{1}$, nessa ordem, enquanto a solução ótima consiste apenas em $T_{0}$ e $T_{1}$ . Um exemplo de uma entrada para $k=3$ é ilustrado à direita.

Os resultados de incompatibilidade mostram que o algoritmo guloso é essencialmente o melhor algoritmo de aproximação de tempo polinomial possível para definir cobertura até termos de ordem inferior (consulte Resultados de incompatibilidade abaixo), sob suposições de complexidade plausíveis. Uma análise mais rigorosa do algoritmo guloso mostra que a razão de aproximação é exatamente $\ln {n}-\ln {\ln {n}}+\Theta (1)$ .

Sistemas de baixa frequência

Se cada elemento ocorre em no máximo f conjuntos, então uma solução pode ser encontrada no tempo polinomial que aproxima o ótimo dentro de um fator de f usando relaxação LP .

Se a restrição $x_{S}\in \{0,1\}$ é substituído por $x_{S}\geq 0$ para todos S em ${\mathcal {S}}$ no programa linear inteiro mostrado acima, então ele se torna um programa linear L (não inteiro). O algoritmo pode ser descrito da seguinte maneira:

1. Encontre uma solução ótima O para o programa L usando algum método de tempo polinomial para resolver programas lineares.
2. Escolha todos os conjuntos S para os quais a variável correspondente x _S tem valor pelo menos 1 / f na solução O

Resultados de inadequação

Quando $n$ refere-se ao tamanho do universo, Lund & Yannakakis (1994) mostraram que a cobertura do conjunto não pode ser aproximada em tempo polinomial dentro de um fator de ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$, a menos que NP tenha algoritmos de tempo quase polinomial . Feige (1998) melhorou este limite inferior para ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ sob as mesmas suposições, o que essencialmente corresponde à razão de aproximação alcançada pelo algoritmo guloso. Raz & Safra (1997) estabeleceram um limite inferior de $c\cdot \ln {n}$, Onde $c$ é uma certa constante, sob a suposição mais fraca de que P $\not =$ NP . Um resultado semelhante com um valor mais alto de $c$ foi recentemente comprovado por Alon, Moshkovitz & Safra (2006) . Dinur & Steurer (2013) mostraram inadequação ideal, provando que não pode ser aproximado de ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ a menos que P $=$ NP .

Cobertura de conjuntos ponderada

Relaxando o programa linear inteiro para cobertura de conjunto ponderado declarado acima, pode-se usar o arredondamento aleatório para obter um $O(\log n)$ - aproximação de fator. A análise correspondente para cobertura de conjunto não ponderada é delineada em Arredondamento aleatório # Algoritmo de arredondamento aleatório para cobertura de conjunto e pode ser adaptada ao caso ponderado.

Problemas relacionados

• Conjunto de acerto é uma reformulação equivalente do Set Cover.
• A cobertura do vértice é um caso especial de conjunto de acerto.
• A cobertura de arestas é um caso especial de capa de conjunto.
• A cobertura geométrica do conjunto é um caso especial de cobertura do conjunto quando o universo é um conjunto de pontos em $\mathbb {R} ^{d}$ e os conjuntos são induzidos pela interseção do universo e formas geométricas (por exemplo, discos, retângulos).
• Definir embalagem
• O problema de cobertura máxima é escolher no máximo k conjuntos para cobrir o máximo de elementos possível.
• Conjunto dominante é o problema de selecionar um conjunto de vértices (o conjunto dominante) em um gráfico de forma que todos os outros vértices sejam adjacentes a pelo menos um vértice no conjunto dominante. O problema do conjunto dominante foi mostrado como NP completo por meio de uma redução da cobertura do conjunto.
• O problema exato da cobertura é escolher uma cobertura de conjunto sem nenhum elemento incluído em mais de um conjunto de cobertura.

Referências

• Alon, Noga; Moshkovitz, Dana; Safra, Shmuel (2006), «Algorithmic construction of sets for k-restrictions», ACM Trans. Algorithms, ISSN 1549-6325, 2 (2): 153–177, doi:10.1145/1150334.1150336 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, ISBN 978-0-262-03293-3, Cambridge, Mass.: MIT Press and McGraw-Hill, pp. 1033–1038  Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, ISBN 978-0-262-03293-3, Cambridge, Mass.: MIT Press and McGraw-Hill, pp. 1033–1038 
• Feige, Uriel (1998), «A threshold of ln n for approximating set cover», Journal of the ACM, ISSN 0004-5411, 45 (4): 634–652, doi:10.1145/285055.285059  .
• Karpinski, Marek; Zelikovsky, Alexander (1998), Approximating dense cases of covering problems, ISBN 9780821870846, 40, pp. 169–178  Karpinski, Marek; Zelikovsky, Alexander (1998), Approximating dense cases of covering problems, ISBN 9780821870846, 40, pp. 169–178 
• Lund, Carsten; Yannakakis, Mihalis (1994), «On the hardness of approximating minimization problems», Journal of the ACM, ISSN 0004-5411, 41 (5): 960–981, doi:10.1145/185675.306789  .
• Raz, Ran; Safra, Shmuel (1997), «A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP», STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ISBN 978-0-89791-888-6, ACM, pp. 475–484  Raz, Ran; Safra, Shmuel (1997), «A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP», STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ISBN 978-0-89791-888-6, ACM, pp. 475–484  .
• Dinur, Irit; Steurer, David (2013), «Analytical approach to parallel repetition», STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing, ACM, pp. 624–633  .
• Vazirani, Vijay V. (2001), Approximation Algorithms (PDF), ISBN 978-3-540-65367-7, Springer-Verlag  Vazirani, Vijay V. (2001), Approximation Algorithms (PDF), ISBN 978-3-540-65367-7, Springer-Verlag 
• Korte, Bernhard; Vygen, Jens (2012), Combinatorial Optimization: Theory and Algorithms, ISBN 978-3-642-24487-2 5 ed. , Springer  Korte, Bernhard; Vygen, Jens (2012), Combinatorial Optimization: Theory and Algorithms, ISBN 978-3-642-24487-2 5 ed. , Springer 
• Cardoso, Nuno; Abreu, Rui (2014), An Efficient Distributed Algorithm for Computing Minimal Hitting Sets (PDF), Graz, Austria, doi:10.5281/zenodo.10037 

Ligações externas

• Benchmarks com soluções ótimas ocultas para cobertura de conjuntos, embalagem de conjuntos e determinação do vencedor
• Um compêndio de problemas de otimização NP - Cobertura mínima do conjunto