10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Have you made any progress on the problem? $\endgroup$ – Yuval Filmus May 29 '13 at 15:52
  • $\begingroup$ I forgot to mention that $A_1 \leq A_2 \leq ... \leq A_k$ $\endgroup$ – gprime May 29 '13 at 16:15
  • $\begingroup$ Related problem, also without a satisfactory answer. (It may not be clear at first glance how they're related, but if $K=2N$, the problem is equivalent to finding a permutation of $1 \ldots 2N$ so that $i_{2a-1} - i_{2a} = A_i$. $\endgroup$ – Peter Shor Jun 6 '13 at 3:58
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

Here is a hint to get you started: since the sum of all numbers from $1$ to $2k$ is exactly $k(2k+1)$, a solution is possible only if in fact $i_1 + i_2 = A_1$, $i_3 + i_4 = A_2$ and so on. So given $i_1$ we know $i_2$, and so on. Also, $3 \leq A_j \leq 4k-1$.

$\endgroup$
  • $\begingroup$ So how should I choose $i_1$ to begin with? Im not seeing the solution. But thanks for the property $3 \leq A_j \leq 4k -1$ $\endgroup$ – gprime May 29 '13 at 16:25
  • 2
    $\begingroup$ If the $A_i$ are sorted, we know $3 \leq A_1$, $10 \leq A_1 + A_2$, $21 \leq A_1 + A_2 + A_3$, and so forth. Are these criteria, together with $\sum_i A_i = k(2k+1)$, enough? If they are, there might possibly be a simple algorithm for this problem. $\endgroup$ – Peter Shor May 29 '13 at 16:33
  • $\begingroup$ Yeah, they are sorted. I will try to use this... $\endgroup$ – gprime May 29 '13 at 16:46
  • $\begingroup$ @PeterShor You must also consider limits from the opposite direction, i.e. $4n-1 \geq A_n, 8n-6 \geq A_{n-1}+A_{n}$, and so on and so forth. Looking at the problem anecdotally, it appears a simple greedy algorithm should discover solutions when they exist, and fail precisely when they don't - but I'm having trouble proving it. $\endgroup$ – torquestomp May 29 '13 at 16:59
  • $\begingroup$ @torquestomp: You're raising a good point. In fact, the limits from one direction also imply the limits from the other, but that's not at all obvious at first sight. I looked at a similar problem, and couldn't figure out a simple algorithm (but it also looked to me like the analog of these criteria was indeed enough). $\endgroup$ – Peter Shor May 29 '13 at 17:01
0
$\begingroup$

It's a matching problem, and so can be solved using Edmond's algorithm. See wikipedia

$\endgroup$
  • 1
    $\begingroup$ The Stackexchange idea is to have a Q&A that's as complete as reasonably possible. Would you be able to expand you answer to be more than just a link to wikipedia? $\endgroup$ – Luke Mathieson May 30 '13 at 4:00
  • $\begingroup$ Can you elaborate? I am failing to see how i can use that algorithms to solve my question. $\endgroup$ – gprime May 31 '13 at 18:58
  • 1
    $\begingroup$ Actually, to me it looks like a special case of 3-matching, which is NP-complete. This doesn't mean that the OPs problem is NP-complete. $\endgroup$ – Peter Shor Jun 1 '13 at 11:34
  • $\begingroup$ Could it be maybe a bipartite matching? I will look into the 3-matching to see if i can figure it out. Thanks! $\endgroup$ – gprime Jun 2 '13 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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