Outra variante de PARTITION

Eu tenho uma redução do seguinte problema de partição para um determinado problema de agendamento:

Entrada: Uma lista de números inteiros positivos em ordem não decrescente. $a_1\leqslant\cdots\leqslant a_n$

Pergunta: Existe um vetor tal que $(x_1,\ldots,x_n)\in\{-1,1\}^n$

\sum_{Eu = 1}^{n} {uma}_{Eu} x_{Eu} = 0 0 e

$\sum_{i=1}^na_ix_i=0\qquad\text{and}$

\sum_{Eu = 1}^{k} {uma}_{Eu} x_{Eu} ⩾ 0 0 para todos k \in {1, ..., n}

$\sum_{i=1}^ka_ix_i\geqslant 0\quad\text{for all }k\in\{1,\ldots,n\}$

Sem a segunda condição, é apenas PARTITION, portanto, NP-hard. Mas a segunda condição parece fornecer muitas informações adicionais. Gostaria de saber se existe uma maneira eficiente de decidir essa variante. Ou ainda é difícil?

cc.complexity-theory reference-request partition-problem subset-sum Thomas Kalinowski
fonte

Respostas:

Aqui está uma redução de PARTITION para esse problema. Seja uma instância de PARTITION. Suponha que . $(a_1,\dots, a_n)$ $a_1\leq a_2\leq \dots \leq a_n$

Seja um "número muito grande", por exemplo, . Considere a instância do nosso problema. $N$ $N = (\sum_{i=1}^n |a_i|) + 1$

\underset{5 n vezes}{\underset{⏟}{N, ..., N}}, N + {uma}_{1}, ..., N + {uma}_{n}, \underset{n vezes}{\underset{⏟}{4 N, ..., 4 N}}

$\underbrace{N, \dots, N}_{5n \text{ times}}, N + a_1, \dots, N+a_n,\underbrace{4N, \dots, 4N}_{n \text{ times}}$

Se houver uma solução para PARTITION, é uma solução para o nosso problema. $x_1,\dots, x_n$
$\underset{4 n vezes}{\underset{⏟}{1, ..., 1}}, - x_{1}, ..., - x_{n}, x_{1}, ..., x_{n}, \underset{n vezes}{\underset{⏟}{- 1, ..., - 1}}$ $\underbrace{1, \dots, 1}_{4n \text{ times}},-x_1,\dots,-x_n,x_1,\dots,x_n,\underbrace{-1,\dots,-1}_{n \text{ times}}$
$(x_1,\dots,x_{5n},y_1,\dots, y_n, z_1,\dots,z_n)$ $\sum_{i=1}^n a_i y_i \equiv 0 \pmod N$
$\sum_{Eu = 1}^{n} {uma}_{Eu} y_{Eu} = 0$ $\sum_{i=1}^n a_i y_i = 0.$ $(y_1,\dots, y_n)$

Yury
fonte

Obrigado Yury. Na minha aplicação, é essencial que a lista de entrada seja ordenada de maneira não decrescente, e a entrada na sua redução não é. Modificarei a pergunta para tornar o requisito do pedido mais explícito.

(N, a_{1}, \dots, a_{n}, N)

$(N,a_1,\ldots,a_n,N)$

Thomas Kalinowski

@ Thomas: Eu não percebi isso. Agora eu atualizei minha solução.

Yury