# 3-partition problem without the restriction to triplets

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

• 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. – domotorp Oct 25 at 7:47
• @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. – Erel Segal-Halevi Oct 26 at 17:58
• I think domotorp answered the question as asked. Maybe edit the question to clarify if that's not the question you had in mind? – Neal Young Oct 27 at 19:55
• @NealYoung done – Erel Segal-Halevi Oct 28 at 12:48
• @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$). – Marzio De Biasi Oct 30 at 16:51