Teilmengenproblem mit vielen Teilbarkeitsbedingungen

Sei eine Menge natürlicher Zahlen. Wir betrachten unter der Teilbarkeits-Teilordnung, dh . Lassen$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 $\}$ .

Was können wir über die Komplexität des Problems in Bezug auf \ alpha (S) sagen, wenn wir das Teilmengen-Summenproblem betrachten, bei dem sich die Mehrfachmenge von Zahlen in $S$ befindet ? Es ist einfach zu sehen, ob \ alpha (S) = 1 ist , dann ist das Problem einfach. Beachten Sie, dass es auch für das schwierigere Rucksackproblem einfach ist, wenn \ alpha (S) = 1 ^{\ Dolch ist} .$\alpha(S)$$\alpha(S)=1$$\alpha(S)=1$^$\dagger$

---

$\dagger$ Sequentielle Rucksackprobleme lösen von M. Hartmann und T. Olmstead (1993)

Dieses Problem kann in Polynomialzeit durch lineare Programmierung gelöst werden, und dies gilt tatsächlich für jede Teilordnung $(S,\le)$ . Übrigens können wir durch Induktion beweisen, dass es für jede endliche Teilordnungsmenge $(S,\le)$ eine endliche Menge $S'\subseteq\mathbb{N}$ und eine Bijektion $f:S\rightarrow S'$ , so dass für alle $s_1,s_2\in S, s_1\le s_2 \Leftrightarrow f(s_1) | f(s_2)$ .

Sei $\mathcal{C}$ die Menge, die durch die Ketten in $S$ . Denken Sie daran, dass $C$ eine Kette iff für alle $v,v'$ in $C$ , $v\le v'$ oder $v'\le v$

Erstellen für jedes eine boolesche Variable für jede Kette eine boolesche Variable . Wir können das folgende lineare Programm für unser Problem schreiben : $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}$$

und sein Dual :$(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}$$

Dann ist das Problem, die minimale Deckung eines bestellten Satzes durch Ketten zu finden, das Doppelte unseres Problems. Der Satz von Dilworth besagt das

Es gibt eine Antikette A und eine Aufteilung der Ordnung in eine Familie P von Ketten, so dass die Anzahl der Ketten in der Aufteilung der Kardinalität von A entspricht

was bedeutet, dass die optimale Lösung dieser beiden Probleme übereinstimmt:$Opt(P)=Opt(D)$

Sei ( bzw. ) die Relaxation von ( bzw. ), dh dasselbe lineare Programm, in dem alle Bedingungen ( bzw. ) werden durch ( bzw. ) ersetzt. Sei und ihre optimale Lösung. Seit wir: und schwache Dualität Theorem legt fest, dass$(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^*)$dann, indem wir alles zusammensetzen, haben wir: $$Opt(P)= Opt(P^*)=Opt(D^*)=Opt(D)$$

Dann können wir mit der Ellipsoidmethode ( ) in Polynomzeit berechnen. Es gibt eine exponentielle Anzahl von Einschränkungen, aber es gibt ein Polynom-Zeittrennungs-Orakel. In der Tat können wir bei gegebener Lösung alle Paare aufzählen und prüfen, ob oder , und daher in polynomieller Zeit entscheiden, ob durchführbar ist oder auf andere Weise die mit der Kette verbundene Beschränkung ist verletzt.$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\}$