Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 14 down vote accepted

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.

share|cite|improve this answer
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 Apr 29 '14 at 3:18
@thomas: I didn't notice that. Now I updated my solution. – Yury Apr 29 '14 at 3:41
Cool. Thanks a lot. – Thomas Kalinowski Apr 29 '14 at 3:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.