Eine andere Variante von PARTITION

Ich habe eine Reduzierung des folgenden Partitionsproblems auf ein bestimmtes Planungsproblem:

Eingabe: Eine Liste positiver Ganzzahlen in nicht absteigender Reihenfolge. $a_1\leqslant\cdots\leqslant a_n$

Frage: Gibt es einen Vektor so dass $(x_1,\ldots,x_n)\in\{-1,1\}^n$

\sum_{i = 1}^{n} a_{i} x_{i} = 0 and

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

\sum_{i = 1}^{k} a_{i} x_{i} ⩾ 0 for all k \in {1, \dots, n}

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

Ohne die zweite Bedingung ist es nur PARTITION, daher NP-hart. Die zweite Bedingung scheint jedoch viele zusätzliche Informationen zu liefern. Ich frage mich, ob es eine effiziente Möglichkeit gibt, diese Variante zu entscheiden. Oder ist es immer noch schwer?

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

Antworten:

Hier ist eine Reduktion von PARTITION auf dieses Problem. Sei $(a_1,\dots, a_n)$ eine Instanz von PARTITION. Angenommen, $a_1\leq a_2\leq \dots \leq a_n$ .

Sei $N$ eine "sehr große Zahl", zB $N = (\sum_{i=1}^n |a_i|) + 1$ . Betrachten Sie die Instanz

\underset{5 n times}{\underset{⏟}{N, \dots, N}}, N + a_{1}, \dots, N + a_{n}, \underset{n times}{\underset{⏟}{4 N, \dots, 4 N}}

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

Gibt es eine Lösung $x_1,\dots, x_n$ für PARTITION, dann
$\underset{4 n times}{\underset{⏟}{1, \dots, 1}}, - x_{1}, \dots, - x_{n}, x_{1}, \dots, x_{n}, \underset{n times}{\underset{⏟}{- 1, \dots, - 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}}$ ist eine Lösung für unser Problem.
Wenn es eine Lösung $(x_1,\dots,x_{5n},y_1,\dots, y_n, z_1,\dots,z_n)$ für die Instanz unseres Problems gibt (auf die wir eine Instanz von PARTITION reduziert haben), dann $\sum_{i=1}^n a_i y_i \equiv 0 \pmod N$ . Also ist
$\sum_{i = 1}^{n} a_{i} y_{i} = 0.$ $\sum_{i=1}^n a_i y_i = 0.$ Das heißt, $(y_1,\dots, y_n)$ ist eine Lösung für PARTITION.

Yury
quelle

Vielen Dank, Yury. In meiner Anwendung ist es wichtig, dass die Eingabeliste nicht absteigend geordnet ist und die Eingabe in Ihrer Reduktion nicht. Ich werde die Frage ändern, um die Bestellanforderung deutlicher zu machen.

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

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

Thomas Kalinowski

@thomas: Das habe ich nicht bemerkt. Jetzt habe ich meine Lösung aktualisiert.

Yury