# Partition into pairs with minimum absolute difference, NP-hard?

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?

• Can we reduce it to a P problem then? Nov 14 '19 at 23:38
• What's the source where you encountered this problem? Do the pairs have to be disjoint?
– D.W.
Nov 15 '19 at 4:21
• It is a special case of some problem I am trying to solve. Yes, the pairs have to be disjoint. Nov 15 '19 at 4:45
• 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. Nov 15 '19 at 7:54

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.
• 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? Nov 15 '19 at 5:01
• @user199027 You can scale the problem by multiplying a large number, so it doesn't matter whether $t_i\le 1$. Nov 15 '19 at 5:06
• 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? Nov 16 '19 at 4:17
• @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$. Nov 16 '19 at 6:49