Algoritmos de tempo pseudo-polinomial mais rápidos para PARTITION

Eu quero particionar N dados (pode ou não ser igual) em 2 subconjuntos, de modo que os 2 subconjuntos tenham a soma o mais próximo possível e também a cardinalidade dos conjuntos seja igual (se n for par) ou diferir apenas por 1 ( se n for ímpar).

Acho que podemos fazer isso no tempo pseudo-polinomial , onde é a soma dos números no conjunto. $O(n^2 A)$ $A$

Posso fazer melhor que isso? Ou seja, existe um algoritmo de tempo pseudo-polinomial que é executado no tempo $O(n^c A)$ com $c < 2$ ?

Desde já, obrigado!

ds.algorithms co.combinatorics partition-problem Firebrandt
fonte

Observe que, como um caso especial da mochila, ela possui um FPTAS . Veja, por exemplo, o ELLawler. Algoritmos de aproximação rápida para problemas de mochila .

Mathieu Chapelle

@Oleksandr, por melhor, quis dizer que existe um algoritmo pseudo-polinomial que roda em O (nA). desculpe por não conseguir postar em látex.

Firebrandt

Receio que esta questão esteja na fronteira de ser muito elementar. Por exemplo, "O problema da Partição com a restrição adicional de que os dois conjuntos devem ter cardinalidade igual ainda está completo-NP?" pode ser uma pergunta típica da lição de casa e tenho medo de que escrever a resposta possa ter um impacto negativo em alguns cursos de complexidade computacional.

Tsuyoshi Ito 30/01

Como isso é muito elementar? A abordagem óbvia fornece , e a questão é se existe um algoritmo melhor em execução no tempo que . Meu palpite é que essa é uma pergunta em aberto.

O (n^{2} A)

$O(n^2A)$

O (n^{c} A)

$O(n^c A)$

c < 2

$c < 2$

quer

@Febrebrandt: Tomei a liberdade de editar sua pergunta original para adicionar minha versão do seu esclarecimento (alterar para com , pois acho que mesmo essa é provavelmente uma pergunta em aberto). Sinta-se à vontade para alterá-lo novamente para se desejar. Penso que a questão, conforme esclarecida pelos seus comentários, é claramente de nível de pesquisa.

O (n A)

$O(nA)$

O (n^{c} A)

$O(n^cA)$

c < 2

$c<2$

O (n A)

$O(nA)$

Peter Shor

Respostas:

Pode-se resolver o problema de decisão em . $\tilde{O}(nA)$

Deixe que a sequência de números ser . Defina como um conjunto tal que se existir uma subsequência de de comprimento que seja igual a . Se , precisamos apenas de tempo adicional para completo para resolver o seu problema. $S$ $F_S$ $(i,j)\in F_S$ $S$ $j$ $i$ $F_S$ $O(nA)$ $F_S$

Se e são duas subsequências que particionam , então $S_1$ $S_2$ $S$

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

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

onde é a soma de minkowski e a adição entre as tuplas é definida em termos de coordenadas. $A+B=\{a+b | a\in A, b\in B\}$

Reivindicação: Computar de e leva . $F_S$ $F_{S_1}$ $F_{S_2}$ $\tilde{O}(|S|A)$

Prova: aplique convolução 2D em duas tabelas de tamanho. $A\times |S|$

O algoritmo particiona a sequência em duas seqüências de tamanho igual, aplica recursão a cada uma e obtém a soma minkowski do resultado. Seja o pior caso de tempo de execução quando a entrada do algoritmo tiver elementos e for um limite superior da soma. Temos que mostra . $T_A(n)$ $n$ $A$

T_{UMA} (n) = 2 T_{UMA} (n / 2) + UMA \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)$

O escondidos fator é . $\log$ $\log n \log nA$

Chao Xu
fonte

Se alguém se importa com os fatores de , com uma análise cuidadosa, podemos provar que a complexidade do tempo para o algoritmo de Chao é . $\log$ $O(nA\log(nA))$

Prova. Na nona camada da árvore de recursão, dividimos o conjunto em dois conjuntos de tamanho igual e , o que fornece $S$ $S_1$ $S_2$

T_{e} (n, UMA) = T_{o} (n / 2, {UMA}^{'}) + T_{o} (n / 2, UMA - {UMA}^{'}) + O (n UMA registro (n UMA)),

$T_e(n,A)=T_o(n/2,A')+T_o(n/2,A-A')+O(nA\log(nA)),$ e na camada ímpar da árvore de recursão, particionamos o conjunto

em dois conjuntos "igualmente somados"

. Para ser mais preciso, podemos particionar um conjunto

com a soma

em dois conjuntos

com cada um deles somando

, com no máximo um elemento restante. Podemos lidar com esse elemento com programação dinâmica trivial em

. Isso fornece

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)$

que

. Portanto, temos

T_{o} (n, UMA) = T_{e} (n_{1}, UMA / 2) + T_{e} (n - n_{1}, UMA / 2) + O (n UMA registro (n UMA)),

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

onde

, e

. Isso nos dará

T (n, UMA) \leq \sum_{Eu = 1}^{4} T (n_{Eu}, {UMA}_{Eu}) + O (n UMA registro (n UMA)),

$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
fonte