Sea un conjunto de números naturales. Consideramos bajo el orden parcial de divisibilidad, es decir, . Dejar
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 .
Resolviendo problemas de mochila secuenciales por M. Hartmann y T. Olmstead (1993)
Respuestas:
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,≤) S′⊆N f:S→S′ s1,s2∈S,s1≤s2⇔f(s1)|f(s2)
Let el conjunto formado por las cadenas en . Recuerde que es una cadena iff para todos en , oC S C v,v′ C v≤v′ v′≤v
Ahora crear una variable booleana para cada , y una variable booleana para cada cadena . Podemos escribir el siguiente programa lineal para nuestro problema:xv v∈S yC C (P)
y su doble :(D)
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]
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) X s1,s2∈X s1≤s2 s2≤s1 X {v1,v2}
fuente