Another variant of PARTITION

Question

I've got a reduction of the following partition problem to a certain scheduling problem:

Input: A list $a_1\leqslant\cdots\leqslant a_n$ of positive integers in non-decreasing order.

Question: Does there exist a vector $(x_1,\ldots,x_n)\in\{-1,1\}^n$ such that

\[\sum_{i=1}^na_ix_i=0\qquad\text{and}\] \[\sum_{i=1}^ka_ix_i\geqslant 0\quad\text{for all }k\in\{1,\ldots,n\}\]

Without the second condition it's just PARTITION, hence NP-hard. But the second condition seems to provide a lot of additional information. I'm wondering if there is an efficient way of deciding this variant. Or is it still hard?

Answer 1

Here is a reduction from PARTITION to this problem. Let $(a_1,\dots, a_n)$ be an instance of PARTITION. Assume that $a_1\leq a_2\leq \dots \leq a_n$.

Let $N$ be a “very large number”, e.g. $N = (\sum_{i=1}^n |a_i|) + 1$. Consider the instance $$\underbrace{N, \dots, N}_{5n \text{ times}}, N + a_1, \dots, N+a_n,\underbrace{4N, \dots, 4N}_{n \text{ times}}$$ of our problem.

1. If there is a solution $x_1,\dots, x_n$ to PARTITION then $$\underbrace{1, \dots, 1}_{4n \text{ times}},-x_1,\dots,-x_n,x_1,\dots,x_n,\underbrace{-1,\dots,-1}_{n \text{ times}}$$ is a solution to our problem.

2. If there is a solution $(x_1,\dots,x_{5n},y_1,\dots, y_n, z_1,\dots,z_n)$ to the instance of our problem (which we reduced an instance of PARTITION to), then $\sum_{i=1}^n a_i y_i \equiv 0 \pmod N$. Thus $$\sum_{i=1}^n a_i y_i = 0. $$ That is, $(y_1,\dots, y_n)$ is a solution to PARTITION.