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$
8
  • 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, 2020 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$ Oct 26, 2020 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, 2020 at 19:55
  • $\begingroup$ @NealYoung done $\endgroup$ Oct 28, 2020 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$ Oct 30, 2020 at 16:51

0

Your Answer

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

Browse other questions tagged or ask your own question.