# Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?

From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $$S$$ of $$n$$ integers, and an integer $$m$$, the goal is to construct $$m$$ subsets such that each subset sums to a capacity $$c$$.

There are several variants for the optimization of the MSSP. Here, we are interested in the max-sum variant: for each subset $$j$$ in $$\{1,\dots, m\}$$ there is a capacity $$C_j$$. The goal is to make the sum of all subsets as large as possible, such that the sum in each subset $$j$$ is at most $$C_j$$.

• When $$m$$ is a part of the input, there is no FPTAS unless $$P=NP$$, by reduction from 3-partition.
• When $$m$$ is fixed, even when $$m=2$$, there is no FPTAS unless $$P=NP$$. by reduction from equal-cardinality partition problem.

What happens when $$m = 2$$ (fixed) and $$c=\frac{\sum_{x \in S}}{3}$$ for the two subsets? $$c$$ is no longer a part of the input, but it is not fixed as well: it depends on the multiset $$S$$.

Let us define the problem as follows: given a multiset $$S$$, the goal is to make 2 subsets with sum as large as possible, such that the sum in each subset is at most $$\frac{\sum_{x \in S}}{3}$$.

Questions:

• Has a similar problem been studied?
• Does it have an FPTAS?