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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you made any progress on the problem? $\endgroup$
    – Yuval Filmus
    Commented May 29, 2013 at 15:52
  • $\begingroup$ I forgot to mention that $A_1 \leq A_2 \leq ... \leq A_k$ $\endgroup$
    – gprime
    Commented May 29, 2013 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
    Commented Jun 6, 2013 at 3:58

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
0
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$.

Improve this answer
$\endgroup$
6
  • $\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
    Commented May 29, 2013 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
    Commented May 29, 2013 at 16:33
  • $\begingroup$ Yeah, they are sorted. I will try to use this... $\endgroup$
    – gprime
    Commented May 29, 2013 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
    Commented May 29, 2013 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
    Commented May 29, 2013 at 17:01
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 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
    Commented May 30, 2013 at 4:00
  • $\begingroup$ Can you elaborate? I am failing to see how i can use that algorithms to solve my question. $\endgroup$
    – gprime
    Commented May 31, 2013 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
    Commented Jun 1, 2013 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
    Commented Jun 2, 2013 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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