Algoritmos de tiempo pseudo-polinomiales más rápidos para PARTICIÓN

Quiero dividir N números dados (pueden o no ser iguales) en 2 subconjuntos de modo que los 2 subconjuntos tengan una suma lo más cercana posible y también la cardinalidad de los conjuntos es igual (si n es par) o difiere solo en 1 ( si n es impar)

Creo que podemos hacer esto en tiempo pseudo polinomial , donde es la suma de números en el conjunto. $O(n^2 A)$ $A$

¿Puedo hacerlo mejor que esto? A saber, ¿hay un algoritmo de tiempo pseudo polinomial que se ejecuta en el tiempo con ? $O(n^c A)$ $c < 2$

¡Gracias por adelantado!

ds.algorithms co.combinatorics partition-problem Firebrandt
fuente

Tenga en cuenta que, como un caso especial de mochila, tiene un FPTAS . Ver, por ejemplo, ELLawler. Algoritmos de aproximación rápida para problemas de mochila .

Mathieu Chapelle

@Oleksandr, por mejor me refería a si hay un algoritmo pseudo polinomial que se ejecuta en O (nA). lo siento, no puedo publicar en látex.

Firebrandt

Me temo que esta pregunta está al borde de ser demasiado elemental. Por ejemplo, "¿El problema de Partición con la restricción adicional de que los dos conjuntos deben tener la misma cardinalidad aún es NP-completo?" puede ser una pregunta típica de tarea y me temo que escribir la respuesta puede tener un impacto negativo en algunos cursos de complejidad computacional.

Tsuyoshi Ito

¿Cómo es esto demasiado elemental? El enfoque obvio da , y la pregunta es si hay un mejor algoritmo en ejecución en el tiempo donde . Mi conjetura es que esta es una pregunta abierta.

O (n^{2} A)

$O(n^2A)$

O (n^{c} A)

$O(n^c A)$

c < 2

$c < 2$

Peter Shor

@Firebrandt: Me tomé la libertad de editar su pregunta original para agregar mi versión de su aclaración (cambiando a con , ya que creo que incluso esa es probablemente una pregunta abierta). Si lo desea , vuelva a cambiarlo a . Creo que la pregunta, como lo aclararon sus comentarios, es claramente de nivel de investigación.

O (n A)

$O(nA)$

O (n^{c} A)

$O(n^cA)$

c < 2

$c<2$

O (n A)

$O(nA)$

Peter Shor

Respuestas:

Uno puede resolver el problema de decisión en . $\tilde{O}(nA)$

Deje que la secuencia de números sea . Defina como un conjunto tal que si existe una subsecuencia de de longitud que sume a . Si hemos calculado , entonces solo necesitamos tiempo adicional para completar para resolver su problema. $S$ $F_S$ $(i,j)\in F_S$ $S$ $j$ $i$ $F_S$ $O(nA)$ $F_S$

Si y son dos subsecuencias que dividen , entonces $S_1$ $S_2$ $S$

F_{S} = F_{S_{1}} + F_{S_{2}}

$F_S = F_{S_1} + F_{S_2}$

donde es la suma minkowski, y la suma entre tuplas se define por coordenadas. $A+B=\{a+b | a\in A, b\in B\}$

Reclamo: desde y lleva tiempo . $F_S$ $F_{S_1}$ $F_{S_2}$ $\tilde{O}(|S|A)$

Prueba: aplique convolución 2D en dos tablas de tamaño. $A\times |S|$

El algoritmo divide la secuencia en dos secuencias de igual tamaño, aplica recursividad a cada una y toma la suma minkowski del resultado. Sea el peor tiempo de ejecución cuando la entrada al algoritmo tiene elementos y es un límite superior de la suma. Tenemos que muestra . $T_A(n)$ $n$ $A$

T_{A} (n) = 2 T_{A} (n / 2) + A \tilde{O} (n)

$T_A(n) = 2 T_A(n/2) + A \tilde{O}(n)$

T_{A} (n) = \tilde{O} (n A)

$T_A(n) = \tilde{O}(n A)$

La oculta factor es . $\log$ $\log n \log nA$

Chao Xu
fuente

Si a alguien le importan los factores , con un análisis cuidadoso podemos probar que la complejidad temporal del algoritmo de Chao es . $\log$ $O(nA\log(nA))$

Prueba. En la capa uniforme del árbol de recursión, dividimos el conjunto en dos conjuntos de igual tamaño y , lo que da y en la capa impar del árbol de recursión, dividimos el conjunto en dos conjuntos "igualmente sumados" y . Para ser precisos, podemos dividir un conjunto con la suma en dos conjuntos y con cada uno de ellos sumando , con como máximo un elemento restante. Podemos lidiar con ese elemento con programación dinámica trivial en $S$ $S_1$ $S_2$

T_{e} (n, A) = T_{o} (n / 2, A^{'}) + T_{o} (n / 2, A - A^{'}) + O (n A \log (n A)),

$T_e(n,A)=T_o(n/2,A')+T_o(n/2,A-A')+O(nA\log(nA)),$

S

$S$

S_{1}

$S_1$

S_{2}

$S_2$

S

$S$

A

$A$

S_{1}

$S_1$

S_{2}

$S_2$

\leq A / 2

$\leq A/2$

O (A)

$O(A)$ . Esto proporciona donde. Por lo tanto, tenemos donde , , y . Esto nos dará .

T_{o} (n, A) = T_{e} (n_{1}, A / 2) + T_{e} (n - n_{1}, A / 2) + O (n A \log (n A)),

$T_o(n,A)=T_e(n_1,A/2)+T_e(n-n_1,A/2)+O(nA\log(nA)),$

n_{1} = | S_{1} |

$n_1=|S_1|$

T (n, A) \leq \sum_{i = 1}^{4} T (n_{i}, A_{i}) + O (n A \log (n A)),

$T(n,A)\leq \sum_{i=1}^4T(n_i,A_i)+O(nA\log(nA)),$

\sum_{i = 1}^{4} n_{i} \leq n

$\sum_{i=1}^4n_i\leq n$

\sum_{i = 1}^{4} A_{i} \leq A

$\sum_{i=1}^4A_i\leq A$

\forall i, n_{i} \leq n / 2, A_{i} \leq A / 2

$\forall i,~n_i\leq n/2,~A_i\leq A/2$

T (n, A) = O (n A \log (n A))

$T(n,A)=O(nA\log(nA))$

hqztrue
fuente