# algorithms – 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$$ is fixed and $$c$$ is defined to be $$frac{sum_{x in S}}{m+1}$$ for every subset? In this case, $$c$$ is not fixed, but it is also not a variable: $$c$$ depends on $$S$$.

The smallest case is when $$m=2$$ and $$c=frac{sum_{x in S}}{3}$$: given a multiset S, the goal is to make two subsets with sum as large as possible, such that the sum in each subset is at most $$frac{sum_{x in S}}{3}$$.

We can call this case of the problem $$frac{1}{3}$$-2-SSP. In general, $$frac{1}{k+1}$$-k-SSP: the goal is to make k subsets with sum as large as possible, such that the sum in each subset is at most $$frac{sum_{x in S}}{k+1}$$.

Questions:

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