2
$\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$
  • $\begingroup$ Can we reduce it to a P problem then? $\endgroup$ – user199027 Nov 14 '19 at 23:38
  • $\begingroup$ What's the source where you encountered this problem? Do the pairs have to be disjoint? $\endgroup$ – D.W. Nov 15 '19 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$ – user199027 Nov 15 '19 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$ – Tom van der Zanden Nov 15 '19 at 7:54
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$
  • $\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$ – user199027 Nov 15 '19 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 Nov 15 '19 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$ – user199027 Nov 16 '19 at 4:17
  • $\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 Nov 16 '19 at 6:49

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.