9
$\begingroup$

In the ABC-partition problem, there are three sets $A, B, C$ with $m$ positive integers in each. The sum of all integers is $m T$. The goal is to construct $m$ triplets with the same sum $T$, each of which contains exactly one integer from $A, B$ and $C$.

The problem "feels" NP-hard, but I could not find a proof for this. I could only find reductions in the wrong direction:

But, none of these reductions shows that ABC-partition is NP hard.

Previously I asked specifically about a reduction from 3-partition from ABC-partition; now I am not even sure if it is NP-hard. Is it?

$\endgroup$
6
  • $\begingroup$ I don't know of a reduction from 3-partition to ABC-partition. But ABC-partition is straightforwardly a special case of 3-dimensional matching (en.wikipedia.org/wiki/3-dimensional_matching), and I think that would make a better source problem to attempt a reduction from. $\endgroup$ Commented Sep 10, 2020 at 22:24
  • $\begingroup$ Show that ABC-partition is NP-hard by reduction from any NP-hard problem, then use the Cook–Levin theorem to obtain a reduction from 3-partition to ABC-partition. $\endgroup$ Commented Oct 25, 2020 at 8:04
  • $\begingroup$ @YuvalFilmus these problems seem so similar, that I thought there may be a more direct reduction. $\endgroup$ Commented Oct 25, 2020 at 8:54
  • $\begingroup$ Is there any particular reason you're interested in such a reduction? $\endgroup$ Commented Oct 25, 2020 at 9:57
  • $\begingroup$ @YuvalFilmus My personal interest is mainly theoretic and educational. But there may be a practical application for approximation algorithms: if you have an approximation algorithm for one problem, then you can use the reduction to get an approximation algorithm for the other. I think it does not follow directly from the fact that both are NP-hard. $\endgroup$ Commented Oct 26, 2020 at 18:03

2 Answers 2

2
$\begingroup$

This seems to be the Numerical 3D matching problem. Wikipedia cites a proof of NP-Hardness by Garey and Johnson (problem SP16).

$\endgroup$
1
  • $\begingroup$ Thanks! I looked at the book. They claim that it is NP-hard by transformation from 3-d matching, but do not provide a proof; they refer to their 1975 article here: epubs.siam.org/doi/abs/10.1137/0204035 but in that article, I did not find any mention of numerical 3-dimensional matching. There is only a reduction from 3-d matching to some job scheduling problem (scheduling jobs on 5 processors with 8 resources; later reduced to scheduling on 3 processors with 1 resource). $\endgroup$ Commented Feb 6 at 12:50
1
$\begingroup$

I did not find the proof claimed by Garey and Johnson at [SP16]. But I found two other proofs, which seem independent (do not rely on the existing proof):

$\endgroup$
1
  • $\begingroup$ This answered the question, it can be marked accepted. It is a follow up to Steven's partial answer 3-week prior. $\endgroup$ Commented Feb 23 at 16:20

Your Answer

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

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