<p>In the standard 3-partition problem, there are <span class="math-container">$3 m$</span> integers, their sum is <span class="math-container">$m T$</span>, and they have to be partitioned into <span class="math-container">$m$</span> subsets of sum <span class="math-container">$T$</span> and size <span class="math-container">$3$</span>.</p>
<p>Consider the variant without the restriction that the size is <span class="math-container">$3$</span> (but with the restriction that there must be <span class="math-container">$m$</span> subsets with a sum of <span class="math-container">$T$</span>). Are these problems computationally equivalent?</p>
<p>[NOTE: often there is an additional restriction that each input number is in <span class="math-container">$(T/4 , T/2)$</span>; in this question there is no such restriction - the numbers in both variants can be any positive integers].</p>
<p>There is an easy reduction from the triplet-variant to the subset-variant: given an instance of the triplet-variant with target-sum <span class="math-container">$T$</span>, construct an instance of the subset-variant by adding <span class="math-container">$2 T$</span> to each element and changing the target-sum to <span class="math-container">$7 T$</span>. 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 <span class="math-container">$6 T$</span> and the sum of every 4-element subset is at least <span class="math-container">$8 T$</span>.</p>
<p>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?</p>
<p>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.</p>
<p><sub>Note: the question was posted in <a href="https://cs.stackexchange.com/q/129944/1342">cs.SE</a> about two months ago - no answer there</sub></p>

CC BY-SA 4.0
2020-10-25T07:47:20.720Z
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
CC BY-SA 4.0
2020-10-26T17:58:32.870Z
@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
CC BY-SA 4.0
2020-10-27T19:55:24.873Z
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
CC BY-SA 4.0
2020-10-28T12:48:09.753Z
@NealYoung done
Erel Segal-Halevi
CC BY-SA 4.0
2020-10-30T16:51:36.267Z
@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
CC BY-SA 4.0
2020-10-31T17:11:09.433Z
@Saeed do you see anything wrong with my reduction?
Erel Segal-Halevi
CC BY-SA 4.0
2020-10-31T20:41:28.413Z
@Saeed: pick $a_1=2, a_2=1, a_3 = 0$, $T=1$
Marzio De Biasi
CC BY-SA 4.0
2020-11-06T13:25:25.457Z
The problem with $m=2$ easily reduces to the problem with any $m>2$ (just add $m-2$ elements of weight $T$).  So to solve the problem for any particular $m\ge 2$, you have to (at least) effectively solve the problem with $m=2$.  This problem is PARTITION.  As a stepping stone towards a full solution, can you find a "direct" reduction from PARTITION to 3-PARTITION as defined in the post?
Neal Young
<reductions><partition-problem>
3-partition problem without the restriction to triplets
Erel Segal-Halevi
# 3-partition problem without the restriction to triplets

(Asked by: username_0 on 2020-10-25)

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](https://cs.stackexchange.com/q/129944/1342) about two months ago - no answer there

**Tags:** reductions, partition-problem

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 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.  
> **username_2**: I think username_1 answered the question as asked.  Maybe edit the question to clarify if that's not the question you had in mind?  
> **username_0**: @NealYoung done  
> **username_3**: @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$).  
> **username_0**: @Saeed do you see anything wrong with my reduction?  
> **username_3**: @Saeed: pick $a_1=2, a_2=1, a_3 = 0$, $T=1$  
> **username_2**: The problem with $m=2$ easily reduces to the problem with any $m>2$ (just add $m-2$ elements of weight $T$).  So to solve the problem for any particular $m\ge 2$, you have to (at least) effectively solve the problem with $m=2$.  This problem is PARTITION.  As a stepping stone towards a full solution, can you find a "direct" reduction from PARTITION to 3-PARTITION as defined in the post?  

---

## 0 answers

