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

Question

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?

Answer 1

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.