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?