Problem Detail: Given $k$ numbers $A_1 leq A_2 leq … leq A_k$ such that $sumlimits_{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
