Multiple subset sum

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 ${\displaystyle S}$ 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 MSSP: for each subset j in 1,...,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.^[1]
• Max-min MSSP (also called bottleneck MSSP or BMSSP): again each subset has a capacity, but now the goal is to make the smallest subset sum as large as possible.^[1]
• Fair SSP: the subsets have no fixed capacities, but each subset belongs to a different person. The utility of each person is the sum of items in his/her subsets. The goal is to construct subsets that satisfy a given criterion of fairness, such as max-min item allocation.