0
$\begingroup$

In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$.

Consider the variant without the restriction that the size is $3$ (but with the restriction that there must be $m$ subsets with a sum of $T$). Are these problems computationally equivalent?

[NOTE: often there is an additional restriction that each input number is in $(T/4 , T/2)$; in this question there is no such restriction - the numbers in both variants can be any positive integers].

There is an easy reduction from the triplet-variant to the subset-variant: given an instance of the triplet-variant with target-sum $T$, construct an instance of the subset-variant by adding $2 T$ to each element and changing the target-sum to $7 T$. Every solution to the triplet-instance is also obviously a solution to the subset-instance. Conversely, in every solution to the subset-instance, each subset must have exactly 3 elements, since the sum of any 2-element subset is at most $6 T$ and the sum of every 4-element subset is at least $8 T$.

Is there a reduction in the opposite direction? Particularly, given an instance of the subset-variant, how can I construct an instance of the triplet-variant, that has a solution whenever the original instance has one?

Note that, since standard 3-partition is NP-hard and the unconstrained partition problem is in NP, there must be a polynomial-time reduction between these problems, maybe going through some other problems. But I am looking for a more direct reduction. Such a direct reduction can be useful, for example, for applying approximation algorithms for one problem (for optimization variants of the problem) to the other one.

Note: the question was posted in cs.SE about two months ago - no answer there

$\endgroup$
  • 3
    $\begingroup$ Your problem is in NP and 3-partition is NP-hard, so you get a reduction from there. Maybe you're looking for a simple reduction, which is, of course, a subjective definition. $\endgroup$ – domotorp Oct 25 at 7:47
  • $\begingroup$ @domotorp a direct reduction can be useful, for example, for approximation algorithms: if you have an approximation algorithm for one problem, it may be useful to know that it can be used for the other problem too. $\endgroup$ – Erel Segal-Halevi Oct 26 at 17:58
  • 1
    $\begingroup$ I think domotorp answered the question as asked. Maybe edit the question to clarify if that's not the question you had in mind? $\endgroup$ – Neal Young Oct 27 at 19:55
  • $\begingroup$ @NealYoung done $\endgroup$ – Erel Segal-Halevi Oct 28 at 12:48
  • $\begingroup$ @Saeed: I think it's NP-hard, the reduction proposed by Erel is ok; another similar one is to set $T' = 3*2^k + T$ and $a_i' = 2^k + a_i$ where $k>\lceil log_2 (T) \rceil$ (informally add a high enough bit to the $a_i$ and set the target sum of the high bits to $3$). $\endgroup$ – Marzio De Biasi Oct 30 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.