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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Can we reduce it to a P problem then? $\endgroup$
    – user199027
    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. ♦
    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$
    – user199027
    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$
    – Tom van der Zanden
    Nov 15, 2019 at 7:54

1 Answer 1

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

Improve this answer
$\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$
    – user199027
    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
    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$
    – user199027
    Nov 16, 2019 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, 2019 at 6:49

Your Answer

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

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