Como é conhecida essa variante do problema de cobertura do conjunto?

A entrada é um universo e uma família de subconjuntos de U , digamos, F ⊆ 2 U . Nós assumimos que os subconjuntos em F pode cobrir U , ou seja, ⋃ E ∈ F E = U .$U$$U$${\cal F} \subseteq 2^U$${\cal F}$$U$$\bigcup_{E\in {\cal F}}E=U$

Uma sequência de cobertura incremental é uma sequência de subconjuntos em , digamos, A = { E 1 , E 2 , … , E | Um | } , isso satisfaz${\cal F}$${\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\}$

1) ,$\forall E\in {\cal A}, E\in {\cal F}$

2) todos os recém-chegado tem nova contribuição, ou seja, , ⋃ i - 1 j = 1 E i ⊊ ⋃ i j = 1 E i ;$\forall i>1$$\bigcup_{j=1}^{i-1}E_i \subsetneq \bigcup_{j=1}^{i}E_i$

O problema é encontrar uma sequência de cobertura incremental de comprimento máximo (ou seja, com o máximo ). Note-se que uma sequência de comprimento máximo deve, eventualmente, cobrir L , ou seja, ⋃ E ∈ Uma E = U .$|{\cal A}|$$U$$\bigcup_{E\in {\cal A}}E=U$

Tentei encontrar um algoritmo ou um algoritmo aproximado para encontrar a sequência de cobertura incremental mais longa. Eu só estava me perguntando o que essa variante do problema de cobertura do conjunto é conhecida como. Obrigado!

Aqui eu mostro que o problema é NP-completo.

Convertemos um CNF em uma instância do seu problema da seguinte maneira. Suponha que as variáveis ​​do CNF sejam x i 's e as cláusulas sejam m C j ' s, onde n < m . Vamos U = ∪ i ( A i ∪ B i ∪ Z i ) onde todos os conjuntos na união são completamente disjuntos. De fato, A i = { a i , j ∣ x i ∈ C j } ∪ { a $n$ $x_i$$m$ $C_j$$n<m$$U=\cup_i (A_i\cup B_i\cup Z_i)$e B i ={ b i , j | x i ∈ C j }∪{ b i , 0 }, enquanto Z i é qualquer conjunto de cardinalidadek=2n+1. Além disso significamZ= ∪ i Z i e correcção para cada Z i uma família crescente de comprimentokdentro dela, indicado por Z i $A_i=\{a_{i,j}\mid x_i\in C_j\}\cup\{a_{i,0}\}$$B_i=\{b_{i,j}\mid x_i\in C_j\}\cup\{b_{i,0}\}$$Z_i$$k=2n+1$$Z=\cup_i Z_i$$Z_i$$k$ paral=1 ..k. Para todas as variáveis x i , adicionamos2kconjuntos para F , cada conjunto da forma A i ∪ Z i , l e B i ∪ Z i , l . Para cada cláusula C j , podemos adicionar um conjunto de M , que contémZ, e para todos os x i ∈ C j elemento{ um i , j$Z_{i,l}$$l=1..k$$x_i$$2k$$\mathcal F$$A_i \cup Z_{i,l}$$B_i \cup Z_{i,l}$$C_j$$\mathcal F$$Z$$x_i\in C_j$$\{a_{i,j}\}$e para cada elemento { b i , j } .$\bar x_i\in C_j$$\{b_{i,j}\}$

Suponha que a fórmula seja satisfatória e fixe uma tarefa satisfatória. Em seguida, escolher os conjuntos da forma A i ∪ Z i , l ou B i ∪ Z i , l , dependendo se x i é verdadeira ou não. Esses são n k conjuntos incrementais. Agora adicione os conjuntos m correspondentes às cláusulas. Eles também aumentam o tamanho, pois as cláusulas são satisfatórias. Finalmente, podemos até mesmo adicionar k mais conjuntos (um para cada variável) para fazer o cover sequence U .$k$$A_i \cup Z_{i,l}$$B_i \cup Z_{i,l}$$x_i$$nk$$m$$k$$U$

Agora, suponha que conjuntos sejam colocados em uma sequência incremental. Observe que no máximo k + 1 conjuntos correspondentes a x i podem ser selecionados para cada x i . Portanto, se não houver conjuntos de cláusulas na sequência incremental, no máximo n ( k + 1 ) poderá ser selecionado, o que é muito pouco. Observe que, assim que um conjunto de cláusulas é selecionado, podemos escolher no máximo dois conjuntos correspondentes a cada x i , um total de no máximo 2 n conjuntos. Portanto, temos que escolher pelo menos$n(k+1)+m$$k+1$$x_i$$x_i$$n(k+1)$$x_i$$2n$conjuntos de variáveis n ( k - 1 ) antes que qualquer conjunto de cláusulas seja selecionado. Mas como podemos escolher no máximo k + 1 para cada x i , isso significa que, para cada um, escolhemos pelo menos 1 , como k = 2 n + 1 . Isso determina o "valor" da variável, portanto, podemos escolher apenas cláusulas "verdadeiras".$n(k-1)$$k+1$$x_i$$1$$k=2n+1$

Atualização: valor alterado de de n para 2 n + 1, conforme apontado por Marzio.$k$$n$$2n+1$

$\mathcal{A}$$\mathcal{B} \subseteq \mathcal{A}$$\bigcup_{X \in \mathcal{B}} X$

$E_1, \ldots, E_m$$\mathcal{B}$$E_i$$\mathcal{B}$$E_i$

$\mathcal{A}$

Este é um problema bastante natural ...

Lembrete rápido: no problema de empacotamento de conjuntos, dada uma família de conjuntos, encontre o subconjunto máximo de conjuntos que atenda a algumas restrições adicionais (por exemplo, nenhum elemento é coberto mais de 10 vezes, etc.).