Problem sumy podzbiorów z wieloma warunkami podzielności

Niech $S$ będzie zbiorem liczb naturalnych. Rozważamy $S$ w częściowej kolejności podzielności, tj. . Pozwolić $s_1 \leq s_2 \iff s_1 \mid s_2$

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

Jeśli weźmiemy pod uwagę problem sumy podzbioru, w którym wieloseksem liczb jest , to co możemy powiedzieć o złożoności problemu związanego z ? Łatwo jest sprawdzić, czy , wtedy problem jest łatwy. Zauważ, że jest to łatwe nawet dla trudniejszego problemu plecakowego, gdy . $S$ $\alpha(S)$ $\alpha(S)=1$ $\alpha(S)=1$ ^$\dagger$

$\dagger$ Rozwiązywanie kolejnych problemów plecakowych M. Hartmanna i T. Olmsteada (1993)

complexity-theory number-theory knapsack-problems

— Chao Xu
źródło

Zamiast „relacji” sugeruję użycie terminów „częściowa kolejność”. Również na minimalnym myśli, problem moneta Frobenius może być istotne (oczywiście, nie wiem, choć)

— Aryabhata

Problem ten można rozwiązać w czasie wielomianowym za pomocą programowania liniowego, i jest to prawdą w przypadku dowolnego rzędu częściowego . Nawiasem mówiąc, możemy udowodnić przez indukcję, że dla dowolnego skończonego zbioru częściowego rzędu istnieje zbiór skończony i bijectcja , taka, że dla wszystkich $(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)$

Niech się zestaw utworzony przez łańcuchy w . Przypomnij, że jest łańcuchem iff dla wszystkich w , lub $\mathcal{C}$ $S$ $C$ $v,v'$ $C$ $v\le v'$ $v'\le v$

Teraz utworzyć zmiennej logicznej każdego oraz zmiennej logicznej każdego łańcucha . Możemy napisać następujący program liniowy dla naszego problemu: $x_v$ $v\in S$ $y_C$ $C$ $(P)$

\begin{aligned} Max \sum_{v \in S.} x_{v} \\ z zastrzeżeniem \sum_{v \in do} & x_{v} \leq 1, \forall do \in do \\ x_{v} \in {0, 1}, v \in S. \end{aligned}

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

i jego dual : $(D)$

\begin{aligned} Min \sum_{do \in do} y_{do} \\ z zastrzeżeniem \sum_{do : v \in do} & y_{do} \geq 1, \forall v \in S. \\ y_{do} \in {0, 1}, do \in do \end{aligned}

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

Zatem problem znalezienia minimalnego pokrycia zamówionego zestawu przez łańcuchy jest podwójny naszego problemu. Twierdzenie Dilwortha stwierdza, że

Istnieje antychaina A i podział rzędu na rodzinę P łańcuchów, tak że liczba łańcuchów w podziale jest równa liczności A

co oznacza, że optymalne rozwiązanie tych dwóch problemów jest zgodne: $Opt(P)=Opt(D)$

Niech ( odpowiednio. ) będzie relaksacją ( odpowiednio. ), tj . Tego samego programu liniowego, w którym wszystkie ograniczenia ( odpowiednio. ) zastępuje się ( odpowiednio $(P^*)$ $(D^*)$ $(P)$ $(D)$ $x_v\in\{0,1\}$ $y_C\in\{0,1\}$ $x_v\in [0,1]$ ). Niech i będą ich optymalnymi rozwiązaniami. Od mamy: $y_C\in [0,1]$ $Opt(P^*)$ $Opt(D^*)$ $\{0,1\}\subseteq [0,1]$ i twierdzenie o słabej dualności ustala, że a następnie łącząc wszystko, mamy:

O p t (P.) \leq O p t ({P.}^{*}) i O p t ({re}^{*}) \leq O p t (re)

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

O p t (P^{*}) \leq O p t (D^{*})

$Opt(P^*)\le Opt(D^*)$

O p t (P.) = O p t ({P.}^{*}) = O p t ({re}^{*}) = O p t (re)

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

— Mathieu Mari
źródło

x

$x$

x

$x$

x

$x$

Dziękujemy za wyjaśnienie, dlaczego wykładnicza liczba ograniczeń nie stanowi problemu, oraz znaczenie dwoistości. Bardzo dobrze!

— DW