3
$\begingroup$

I have a set $S$ of an even number of positive elements $2m$ and $m$ values $t_1,t_2,\ldots,t_m$ where each $t_i\leq1$ for all $i$.

The question is: can you select $m$ disjoint pairs $(a_i,b_i)$ from $S$ such that $|a_i-b_i|\geq t_i$?

I was trying to prove that this problem is NP-hard by a reduction from 3-Partition Problem. I failed because if I choose the numbers as in 3-partition I cannot guarantee that their absolute difference is at least $t_i$.

Do you have any hints?

$\endgroup$
4
  • $\begingroup$ Can we reduce it to a P problem then? $\endgroup$
    – zebda
    Commented Nov 14, 2019 at 23:38
  • $\begingroup$ What's the source where you encountered this problem? Do the pairs have to be disjoint? $\endgroup$
    – D.W.
    Commented Nov 15, 2019 at 4:21
  • $\begingroup$ It is a special case of some problem I am trying to solve. Yes, the pairs have to be disjoint. $\endgroup$
    – zebda
    Commented Nov 15, 2019 at 4:45
  • $\begingroup$ I was mistaken. I thought the value $t_i$ was just a fixed value (not dependent on $i$); in that case, the problem is just matching. $\endgroup$ Commented Nov 15, 2019 at 7:54

1 Answer 1

2
$\begingroup$

You can reduce Numeric 3D Matching (N3DM) to your problem.

Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\{x_1,\ldots,x_m\},Y=\{y_1,\ldots,y_m\},Z=\{z_1,\ldots,z_m\}$, construct $2m$ elements $x_1+2M,\ldots,x_m+2M,M-y_1,\ldots,M-y_m$ and $m$ values $b-z_1+M,\ldots,b-z_m+M$ for your problem, where $M$ is a very large number. Now the constructed instance of your problem has a solution if and only if the instance of N3DM has a solution.

$\endgroup$
4
  • $\begingroup$ Thanks. Is this valid for $t_i\leq1$ for all $i$? Because we must have these constraints in the problem. Maybe if we say that $z_i\geq b+M-1$, can we? $\endgroup$
    – zebda
    Commented Nov 15, 2019 at 5:01
  • $\begingroup$ @user199027 You can scale the problem by multiplying a large number, so it doesn't matter whether $t_i\le 1$. $\endgroup$
    – xskxzr
    Commented Nov 15, 2019 at 5:06
  • $\begingroup$ When solving my problem with your created instance, I end up with $x_i+y_j+z_k\geq b$, how can I conclude that N3DM is solved? It could be the case that $x_i+y_j+z_k>b$, no? $\endgroup$
    – zebda
    Commented Nov 16, 2019 at 4:17
  • 1
    $\begingroup$ @user199027 In N3DM, $b$ must equal to $(\sum x_i+\sum y_j+\sum z_k)/3$ (otherwise the instance has no solution trivially), so when a solution satisfies $x_i+y_j+z_k\ge b$, then it must be $x_i+y_j+z_k= b$. $\endgroup$
    – xskxzr
    Commented Nov 16, 2019 at 6:49

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.