Quelle est cette variante du problème de la couverture définie?

L' entrée est un univers et une famille de sous - ensembles de U , par exemple, F ⊆ 2 U . Nous supposons que les sous - ensembles de F peuvent couvrir U , c. -à- ⋃ E ∈ F E = U .$U$$U$${\cal F} \subseteq 2^U$${\cal F}$$U$$\bigcup_{E\in {\cal F}}E=U$

Une séquence de recouvrement incrémentielle est une séquence de sous-ensembles dans , disons A = { E 1 , E 2 , … , E | A | } , qui satisfait${\cal F}$${\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\}$

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

2) chaque nouveau venu a une nouvelle contribution, c'est-à-dire, , ⋃ 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$

Le problème est de trouver une séquence de recouvrement incrémentielle de longueur maximale (c'est-à-dire avec un maximum ). Notez qu'une séquence de longueur maximale doit finalement couvrir U , à savoir, ⋃ E ∈ A E = U .$|{\cal A}|$$U$$\bigcup_{E\in {\cal A}}E=U$

J'ai essayé de trouver un algorithme ou un algorithme approximatif pour trouver la séquence de recouvrement incrémentielle la plus longue. Je me demandais juste ce que cette variante de problème de couverture d'ensemble connue sous le nom. Je vous remercie!

Ici, je montre que le problème est NP-complet.

Nous convertissons un CNF en une instance de votre problème comme suit. Supposons que les variables du CNF sont x i et les clauses sont m C j , où n < m . Soit U = ∪ i ( A i ∪ B i ∪ Z i ) où tous les ensembles de l'union sont complètement disjoints. En fait, 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)$et B i ={ b i , j ∣ x i ∈ C j }∪{ b i , 0 }, tandis que Z i est tout ensemble de cardinaliték=2n+1. Notons égalementZ= ∪ i Z i et fixons pour chaque Z i une famille croissante de longueurk à l'intérieur, notée 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$ pourl=1 ..k. Pour chaque variable x i , on ajoute2kensembles à F , chaque ensemble de la forme A i ∪ Z i , l et B i ∪ Z i , l . Pour chaque clause C j , nous ajoutons un ensemble à F , qui contientZ, et pour chaqueélément x i ∈ C j { a 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}\}$et pour chaque élément { b i , j } .$\bar x_i\in C_j$$\{b_{i,j}\}$

Supposons que la formule soit satisfaisable et corrige une affectation satisfaisante. Ensuite, choisissez les ensembles de la forme A i ∪ Z i , l ou B i ∪ Z i , l , selon que x i est vrai ou non. Ce sont n k ensembles incrémentaux. Ajoutez maintenant les m ensembles correspondant aux clauses. Celles-ci continuent également d'augmenter la taille, car les clauses sont satisfaisables. Enfin, nous pouvons même ajouter k plusieurs ensembles (une pour chaque variable) pour faire la couverture de séquence U .$k$$A_i \cup Z_{i,l}$$B_i \cup Z_{i,l}$$x_i$$nk$$m$$k$$U$

Supposons maintenant que ensembles soient placés dans une séquence incrémentale. Notez qu'au plus k + 1 ensembles correspondant à x i peuvent être sélectionnés pour chaque x i . Ainsi, s'il n'y a pas d'ensembles de clauses dans la séquence incrémentale, au plus n ( k + 1 ) peut être sélectionné, ce qui est trop peu. Notez que dès qu'un ensemble de clauses est sélectionné, nous pouvons sélectionner au plus deux ensembles correspondant à chaque x i , soit un total d'au plus 2 n ensembles. Par conséquent, nous devons choisir au moins$n(k+1)+m$$k+1$$x_i$$x_i$$n(k+1)$$x_i$$2n$ ensembles de variables avant de sélectionner un ensemble de clauses. Mais comme nous pouvons choisir au plus k + 1 pour chaque x i , cela signifie que pour chacun, nous avons choisi au moins 1 , comme k = 2 n + 1 . Cela détermine la "valeur" de la variable, nous ne pouvons donc choisir que des clauses "vraies".$n(k-1)$$k+1$$x_i$$1$$k=2n+1$

Mise à jour: modification de la valeur de de n à 2 n + 1, comme l'a souligné 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}$

C'est un problème assez naturel ....

Rappel rapide: Dans le problème de regroupement des ensembles, étant donné une famille d'ensembles, trouvez le sous-ensemble maximal d'ensembles, qui respectent une contrainte supplémentaire (par exemple, aucun élément n'est couvert plus de 10 fois, etc.).