Problema de soma de subconjuntos com muitas condições de divisibilidade

28

Seja um conjunto de números naturais. Consideramos sob a ordem parcial de divisibilidade, ou seja, . DeixeiS s 1s 2SSs1s2s1s2

α(S)=max{|V|VS,V e antichain } .

Se considerarmos o problema da soma do subconjunto em que o multiset de números está em S , o que podemos dizer sobre a complexidade do problema relacionado a α(S) ? É simples ver se α(S)=1 , então o problema é fácil. Observe que é fácil mesmo para o problema mais difícil da mochila quando α(S)=1 .


Resolvendo problemas seqüenciais da mochila por M. Hartmann e T. Olmstead (1993)

Chao Xu
fonte
1
Em vez de "relação", sugiro usar os termos "ordem parcial". Além disso, sobre o pensamento mínima, o problema da moeda Frobenius pode ser relevante (claro, não tenho certeza, embora)
Aryabhata

Respostas:

2

Esse problema pode ser resolvido em tempo polinomial usando programação linear, e isso é verdade para qualquer ordem parcial . A propósito, podemos provar por indução que, para qualquer conjunto de ordens parciais finitas , existe um conjunto finito e uma bijeção , de modo que para todos .(S,)(S,)SNf:SSs1,s2S,s1s2f(s1)|f(s2)

Vamos ser o conjunto formado pelas cadeias em . Lembre que é uma cadeia iff para todos os em , ouCSCv,vCvvvv

Agora criar uma variável booleana para cada , e um variável booleana para cada cadeia . Podemos escrever o seguinte programa linear para o nosso problema: xvvSyCC(P)

MaxvSxvsubject tovCxv1,CCxv{0,1},vS

e seu duplo :(D)

MinCCyCsubject toC:vCyC1,vSyC{0,1},CC

Então, o problema de encontrar a cobertura mínima de um conjunto ordenado por cadeias é o dual do nosso problema. O teorema de Dilworth afirma que

Existe um antichain A e uma partição da ordem em uma família P de cadeias, de modo que o número de cadeias na partição seja igual à cardinalidade de A

which means that the optimal solution of these two problems match : Opt(P)=Opt(D)

Let (P) (resp. (D)) be the relaxation of (P) (resp. (D)) i.e. the same linear program where all constraints xv{0,1} (resp. yC{0,1}) are replaced by xv[0,1] (resp. yC[0,1]). Let Opt(P) and Opt(D) be their optimal solutions. Since {0,1}[0,1] we have :

Opt(P)Opt(P) and Opt(D)Opt(D)
and weak duality theorem establishes that Opt(P)Opt(D) then by putting everything together we have :
Opt(P)=Opt(P)=Opt(D)=Opt(D)

Then, using Ellipsoid method, we can compute Opt(P) ( =Opt(P)) in polynomial time. There are an exponential number of constraints but there exists a polynomial time separation oracle. Indeed given a solution X, we can enumerate all couples s1,s2X and check if s1s2 or s2s1, and therefore decide in polynomial time whether X is feasible or otherwise the constraint associated to the chain {v1,v2} is violated.

Mathieu Mari
fonte
Ellispoid method works whatever the number of constraints, if we have (1) a polynomial number of variables and (2) a separation oracle which given any solution x decides in polynomial time whether x is feasible or find a constraints violated by x. I recommend reading [www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf], wikipedia is not very clear on this point
Mathieu Mari
Thanks for explaining why the exponential number of constraints is not a problem, and the relevance of duality. Very nice!
D.W.