4
$\begingroup$

I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$.

The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$?

I was trying to prove that this problem is NP-hard by a reduction from Numerical 3D matching (N3DM).

Given an instance of N3DM; 3 sets $X$, $Y$, $Z$, and a bound $b$, normalize it to make $b=1$. I create an instance of my problem as follows: $S=X\cup Y\cup Z$ and for each $x_i\in X$, set $a_i=x_i+3M$, for each $y_j\in Y$, set $a_j=2M-y_j$, and for each $z_k\in Z$, set $a_k=M-z_k$. $M$ is chosen very large. The idea of this comes from https://cs.stackexchange.com/a/117122/48180.

If N3DM is solved, then $x_i+y_j+z_k=1$, thus $a_i-a_j-a_k=1$ and my problem is solved. But if my problem is solved I cannot prove that N3DM is solved because I could select for example two elements from the same set say $Z$, $x_i+3M-M+z_j-M+z_k=M+x_i+z_j+z_k\geq1$ but N3DM is not solved.

I was saying maybe the problem is easy after all?

Do you have any hints?

$\endgroup$
1
$\begingroup$

If you select two elements from $Z$, then by the pigeonhole principle, there must be a triple that does not contain any element from $Z$, which is impossible.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I think there is a greedy way to solve this.

First, note that the $m$ $a_i$ values of triplets should be the $m$ largest values of $S$.

Then for the $2 m$ remaining values. Follow the decreasing $a_i$ and select the pair ($a_j$, $a_k$) among the remaining values to minimize $D = a_i-a_j-a_k$ respecting $D \ge 1$.

If you cannot there is no solution. This achieves a $O(m^3)$ time complexity.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Neat! Do you have a proof or argument that if this fails there is no solution? $\endgroup$ – D.W. Nov 21 '19 at 17:52
  • $\begingroup$ @D.W. No, and I found a counter example on it : [13, 12, 10 8, 6, 6, 6, 4, 3] which has [(13, 6, 6), (12, 8, 3), (11, 6, 4)] solution but if you greedily select (13, 8, 4) for the first tuplet, you also have 0 regret on it but no global solution. Thus this solution is not working. I will delete it but I let it for the moment, in case it inspires a valid one. $\endgroup$ – Optidad Nov 22 '19 at 9:40

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.