Mathematical optimization problem
The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem. The input to the problem is a multiset formula_1 of "n" integers and a positive integer "m" representing the number of subsets. The goal is to construct, from the input integers, some "m" subsets. The problem has several variants:
Max-sum and max-min MSSP.
When "m" is variable (a part of the input), both problems are strongly NP-hard, by reduction from 3-partition. This means that they have no fully polynomial-time approximation scheme (FPTAS) unless P=NP.
Even when "m"=2, the problems do not have an FPTAS unless P=NP. This can be shown by a reduction from the "equal-cardinality partition problem" (EPART):
The following approximation algorithms are known:
Fair subset sum problem.
The "fair subset sum problem" ("FSSP") is a generalization of SSP in which, after the subset is selected, its items are allocated among two or more agents. The utility of each agent equals the sum of weights of the items allocated to him/her. The goal is that the utility profile satisfies some criterion of fairness, such as the egalitarian rule or the proportional-fair rule. Two variants of the problem are:
Both variants are NP-hard. However, there are pseudopolynomial time algorithms for enumerating all Pareto-optimal solutions when there are two agents:
Nicosia, Pacifici and Pferschy study the price of fairness, that is, the ratio between the maximum sum of utilities, and the maximum sum of utilities in a fair solution:
In both cases, if the item value is bounded by some constant "a", then the POF is bounded by a function of "a".
Multiple knapsack problem.
The multiple knapsack problem (MKP) is a generalization of both the max-sum MSSP and the knapsack problem. In this problem, there are "m" knapsacks and "n" items, where each item has both a value and a weight. The goal is to pack as much value as possible into the "m" bins, such that the total weight in each bin is at most its capacity. 
The MKP has a Polynomial-time approximation scheme.
References.
 ;templatestyles src="Reflist/styles.css" / ;