Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

up vote 13 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|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 Apr 29 at 3:18
    
@thomas: I didn't notice that. Now I updated my solution. –  Yury Apr 29 at 3:41
    
Cool. Thanks a lot. –  thomas Apr 29 at 3:55
add comment

Your Answer

 
discard

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.