Problema de suma de subconjuntos con muchas condiciones de divisibilidad

28

Sea S un conjunto de números naturales. Consideramos S bajo el orden parcial de divisibilidad, es decir, . Dejars1s2s1s2

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

Si consideramos el problema de la suma de subconjuntos donde el conjunto múltiple de números está en , ¿qué podemos decir acerca de la complejidad del problema relacionado con ? Es simple ver si , entonces el problema es fácil. Tenga en cuenta que es fácil incluso para el problema de la mochila más difícil cuando \ dagger .Sα(S)α(S)=1α(S)=1


Resolviendo problemas de mochila secuenciales por M. Hartmann y T. Olmstead (1993)

Chao Xu
fuente
1
En lugar de "relación", sugiero usar los términos "orden parcial". Además, con un pensamiento mínimo, el problema de la moneda Frobenius podría ser relevante (por supuesto, aunque no estoy seguro)
Aryabhata

Respuestas:

2

Este problema se puede resolver en tiempo polinómico usando programación lineal, y esto es realmente cierto para cualquier orden parcial . Por cierto, podemos demostrar por inducción que para cualquier conjunto finito de orden parcial , existe un conjunto finito y una biyección , de modo que para todos .(S,)(S,)SNf:SSs1,s2S,s1s2f(s1)|f(s2)

Let el conjunto formado por las cadenas en . Recuerde que es una cadena iff para todos en , oCSCv,vCvvvv

Ahora crear una variable booleana para cada , y una variable booleana para cada cadena . Podemos escribir el siguiente programa lineal para nuestro problema: xvvSyCC(P)

MaxvSxvsubject tovCxv1,CCxv{0,1},vS

y su doble :(D)

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

Entonces, el problema de encontrar la cobertura mínima de un conjunto ordenado por cadenas es el doble de nuestro problema. El teorema de Dilworth establece que

Existe un antichain A, y una partición del orden en una familia P de cadenas, de modo que el número de cadenas en la partición es igual a la cardinalidad de A

lo que significa que la solución óptima de estos dos problemas coincide:Opt(P)=Opt(D)

Sea ( resp. ) la relajación de ( resp. ), es decir, el mismo programa lineal donde todas las restricciones ( resp. ) se reemplazan por ( resp. ). Deje que y sean sus soluciones óptimas. Como tenemos: y dualidad débil El teorema establece que(P) (D)(P) (D)xv{0,1} yC{0,1}xv[0,1] yC[0,1]Opt(P)Opt(D){0,1}[0,1]

Opt(P)Opt(P) and Opt(D)Opt(D)
Opt(P)Opt(D)luego al poner todo junto tenemos:
Opt(P)=Opt(P)=Opt(D)=Opt(D)

Luego, usando el método Elipsoide , podemos calcular ( ) en tiempo polinómico. Hay un número exponencial de restricciones, pero existe un oráculo de separación de tiempo polinomial. De hecho, dada una solución , podemos enumerar todas las parejas y verificar si o , y, por lo tanto, decidir en tiempo polinómico si es factible o si la restricción asociada a la cadena se viola.Opt(P)=Opt(P)Xs1,s2Xs1s2s2s1X{v1,v2}

Mathieu Mari
fuente
El método de Ellispoid funciona sea cual sea el número de restricciones, si tenemos (1) un número polinómico de variables y (2) un oráculo de separación que, dado cualquier solución, decide en tiempo polinómico si es factible o si encuentra restricciones violadas por . Recomiendo leer [ www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf] , wikipedia no es muy clara en este puntoxxx
Mathieu Mari
Gracias por explicar por qué el número exponencial de restricciones no es un problema y la relevancia de la dualidad. ¡Muy agradable!
DW