1
$\begingroup$

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?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.