Проблема сумм подмножеств со многими условиями делимости

Пусть $S$ множество натуральных чисел. Мы рассматриваем в частичном порядке делимости, т.е. . Позволять$S$$s_1 \leq s_2 \iff s_1 \mid s_2$

$\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, V$ антицепь $\}$ .

Если мы рассмотрим задачу о сумме подмножеств, где мультимножество чисел находится в $S$ , что мы можем сказать о сложности проблемы, связанной с $\alpha(S)$ ? Легко видеть, если $\alpha(S)=1$ , тогда проблема проста. Обратите внимание, что это легко даже для более сложной задачи по ранцу, когда $\alpha(S)=1$^$\dagger$ .

---

$\dagger$ Решение последовательных задач о ранцах М. Хартманном и Т. Олмстедом (1993)

Эта проблема может быть решена за полиномиальное время с помощью линейного программирования, и это действительно верно для любого частичного порядка . Кстати, по индукции можно доказать, что для любого конечного множества частичного порядка существует конечное множество и биекция , такая что для всех .$(S,\le)$$(S,\le)$$S'\subseteq\mathbb{N}$$f:S\rightarrow S'$$s_1,s_2\in S, s_1\le s_2 \Leftrightarrow f(s_1) | f(s_2)$

Пусть множество , образованное цепями в . Напомним, что является цепью тогда и только тогда, когда все в ,$\mathcal{C}$$S$$C$$v,v'$$C$$v\le v'$ или $v'\le v$

Теперь создайте логическую переменную для каждого V ∈ S и булевой переменной у C для каждой цепи С . Мы можем написать следующую линейную программу ( P ) для нашей задачи: Max ∑ v ∈ S x v с учетом ∑ v ∈ C x v ≤ 1 , ∀ C ∈ $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}$$

и его двойной :$(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}$$

Тогда задача нахождения минимального покрытия упорядоченного множества цепями является двойственной нашей задачей. Теорема Дилворта утверждает, что

Существует антицепь A и разбиение порядка на семейство P цепочек, так что число цепей в разбиении равно количеству A

что означает, что оптимальное решение этих двух задач совпадает: $Opt(P)=Opt(D)$

Пусть ( соответственно ( D ∗ ) ) будет релаксацией ( P ) ( соответственно ( D ) ), т.е. той же линейной программы, где все ограничения x v ∈ { 0 , 1 } ( соответственно y C ∈ { 0 , 1 } ) заменяются на x v ∈ [ 0 , 1 ] ( соответственно $(P^*)$ $(D^*)$$(P)$ $(D)$$x_v\in\{0,1\}$ $y_C\in\{0,1\}$$x_v\in [0,1]$ ). Пусть O p t ( P ∗ ) и O p t ( D ∗ ) - их оптимальные решения. Так как { 0 , 1 } ⊆ [ 0 , 1 ] имеем: O p t ( P ) ≤ O p t ( P ∗ )  и  O p t ( D $y_C\in [0,1]$$Opt(P^*)$$Opt(D^*)$$\{0,1\}\subseteq [0,1]$ и теорема о слабой двойственности устанавливает, что O p t ( P ∗ ) ≤ O p t ( D ∗ ), то, собрав все вместе, имеем: O p t ( P ) = O p t ( P ∗ ) = O p t ( D ∗ ) = O p t ( D

$$Opt(P)\le Opt(P^*) \text{ and } Opt(D^*)\le Opt(D)$$ $Opt(P^*)\le Opt(D^*)$ $$Opt(P)= Opt(P^*)=Opt(D^*)=Opt(D)$$

$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\}$