<p>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$.</p>

<p>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. </p>

<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 3.0
2014-04-29T03:18:42.393Z
Thanks Yury. In my application it is essential that the input list is ordered non-decreasingly, and the input $(N,a_1,\ldots,a_n,N)$ in your reduction is not. I'll modify the question to make the order requirement more explicit.
Thomas Kalinowski
CC BY-SA 3.0
2014-04-29T03:41:10.110Z
@thomas: I didn't notice that. Now I updated my solution.
Yury
CC BY-SA 3.0
2014-04-29T02:48:30.667Z
2014-04-29T03:48:22.663Z
2014-04-29T03:48:22.663Z
Yury
<p>I've got a reduction of the following partition problem to a certain scheduling problem:</p>

<p><strong>Input:</strong> A list $a_1\leqslant\cdots\leqslant a_n$ of positive integers in non-decreasing order.</p>

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

<p>\[\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\}\]</p>

<p>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?  </p>

<cc.complexity-theory><reference-request><partition-problem><subset-sum>
Another variant of PARTITION
Thomas Kalinowski
# Another variant of PARTITION

(Asked by: username_0 on 2014-04-28)

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?

**Tags:** cc.complexity-theory, reference-request, partition-problem, subset-sum

---

## 1 answers

### Answer by username_1 on 2014-04-29. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks Yury. In my application it is essential that the input list is ordered non-decreasingly, and the input $(N,a_1,\ldots,a_n,N)$ in your reduction is not. I'll modify the question to make the order requirement more explicit.  
> **username_1**: @thomas: I didn't notice that. Now I updated my solution.  

---

