Problème de sous-ensemble avec de nombreuses conditions de divisibilité

Soit un ensemble de nombres naturels. Nous considérons sous l'ordre partiel de divisibilité, c'est-à-dire s_1 \ leq s_2 \ iff s_1 \ mid s_2 . LaisserS s 1 ≤ s $S$$S$$s_1 \leq s_2 \iff s_1 \mid s_2$

$\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, V$ an antichain $\}$ .

Si nous considérons le problème de la somme des sous-ensembles où le multi-ensemble de nombres est dans $S$ , que pouvons-nous dire de la complexité du problème lié à $\alpha(S)$ ? Il est simple de voir si $\alpha(S)=1$ , alors le problème est facile. Notez qu'il est facile même pour le problème de sac à dos plus difficile lorsque $\alpha(S)=1$^$\dagger$ .

---

$\dagger$ Résolution de problèmes séquentiels de sacs à dos par M. Hartmann et T. Olmstead (1993)

Ce problème peut être résolu en temps polynomial en utilisant une programmation linéaire, et cela est en fait vrai pour tout ordre partiel $(S,\le)$ . Soit dit en passant, nous pouvons prouver par induction que pour tout ensemble d'ordre partiel fini $(S,\le)$ , il existe un ensemble fini $S'\subseteq\mathbb{N}$ et une bijection $f:S\rightarrow S'$ , telle que pour tous $s_1,s_2\in S, s_1\le s_2 \Leftrightarrow f(s_1) | f(s_2)$ .

Que $\mathcal{C}$ l'ensemble formé par les chaînes en $S$ . Rappelez-vous que $C$ est une chaîne ssi pour tout $v,v'$ en $C$ , $v\le v'$ ou $v'\le v$

Maintenant créer une variable booléenne pour chaque , et une variable booléenne pour chaque chaîne . Nous pouvons écrire le programme linéaire suivant pour notre problème: $x_v$$v\in S$$y_C$$C$$(P)$

$$\begin{split} \text{Max} \displaystyle\sum\limits_{v\in S} x_v \\ \text{subject to} \displaystyle\sum\limits_{v\in C} &x_v \le 1, \forall C\in\mathcal{C}\\ &x_v \in \{0,1\}, v\in S \end{split}$$

et son double :$(D)$

$$\begin{split} \text{Min} \displaystyle\sum\limits_{C\in \mathcal{C}} y_C\\ \text{subject to} \displaystyle\sum\limits_{C:v\in C} &y_C \ge 1, \forall v\in S\\ &y_C \in \{0,1\}, C\in \mathcal{C} \end{split}$$

Ensuite, le problème de trouver la couverture minimale d'un ensemble ordonné par chaînes est le double de notre problème. Le théorème de Dilworth déclare que

Il existe une antichaine A, et une partition de l'ordre en une famille P de chaînes, de sorte que le nombre de chaînes dans la partition est égal à la cardinalité de A

ce qui signifie que la solution optimale de ces deux problèmes correspond:$Opt(P)=Opt(D)$

Soit ( resp. ) la relaxation de ( resp. ) ie le même programme linéaire où toutes les contraintes ( resp. ) sont remplacés par ( resp. ). Soit et leurs solutions optimales. Depuis nous avons: et une dualité faible le théorème établit que$(P^*)$ $(D^*)$$(P)$ $(D)$$x_v\in\{0,1\}$ $y_C\in\{0,1\}$$x_v\in [0,1]$ $y_C\in [0,1]$$Opt(P^*)$$Opt(D^*)$$\{0,1\}\subseteq [0,1]$

$$Opt(P)\le Opt(P^*) \text{ and } Opt(D^*)\le Opt(D)$$ $Opt(P^*)\le Opt(D^*)$puis en mettant tout ensemble on a: $$Opt(P)= Opt(P^*)=Opt(D^*)=Opt(D)$$

Ensuite, en utilisant la méthode Ellipsoïde , nous pouvons calculer ( ) en temps polynomial. Il existe un nombre exponentiel de contraintes mais il existe un oracle de séparation temporelle polynomiale. En effet étant donné une solution , on peut énumérer tous les couples et vérifier si ou , et donc décider en temps polynomial si est faisable ou sinon la contrainte associée à la chaîne est violé.$Opt(P^*)$$=Opt(P)$$X$$s_1,s_2\in X$$s_1\le s_2$$s_2\le s_1$$X$$\{v_1,v_2\}$