[Solved]: $2k$ number assignment

Problem Detail: 

Given $k$ numbers $A_1 \leq A_2 \leq ... \leq A_k$ such that $\sum\limits_{i=1}^k A_i = k(2k + 1)$ is there an assignment of numbers $i_1, i_2, ... , i_{2k}$ which is a permutation of $1, 2, ... , 2k$ such that

$i_1 + i_2 \leq A_1\\ i_3 + i_4 \leq A_2\\ .\\.\\.\\ i_{2k-1} + i_{2k} \leq A_k$

?

I cannot find an efficient algorithm and that solves this problem. It seems to be a combinatorial problem. I was unable to find a similar NP-Complete problem. Does this problem look like a known NP-Complete problem or can it be solved with a polynomial algorithm?

Asked By : gprime

Answered By : Peter Shor

This problem is strongly NP-complete.

Suppose all the $A_j$ are odd. Then we know that since $i_{2j-1} + i_{2j} = A_j$ is odd, one of $i_{2j-1}$ and $i_{2j}$ is even and the other is odd. We can assume that $i_{2j-1}$ is odd and $i_{2j}$ is even. By letting $\pi_j = \frac{1}{2}(i_{2j-1}+1)$ and $\sigma_j = \frac{1}{2}(i_{2j})$, we can show that this is equivalent to asking for two permutations, $\pi$ and $\sigma$, of the numbers $1 \ldots n$ such that $\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$.

This problem is known to be NP-complete; see this cstheory.se problem and this paper of W. Yu, H. Hoogeveen, and J. K. Lenstra referenced in the answer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12359

 Ask a Question

 Download Related Notes/Documents