Multiple subset sum

The multiple subset sum problem is an <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a> in <a href="/facts/Computer_science/lN3pEyPz">computer science</a> and <a href="/facts/Operations_research/H5yJkV5n">operations research</a>. It is a generalization of the <a href="/facts/Subset_sum_problem/Guvrwy0L">subset sum problem</a>. The input to the problem is a <a href="/facts/Multiset/bPFJGMDo">multiset</a> 
 
 
 
 S
 
 
 {\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:

<ul><li>Max-sum MSSP: for each subset j in 1,...,m, there is a capacity Cj. 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 Cj.</li>
<li>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.</li>
<li>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 <a href="/facts/Max-min_item_allocation/LWq3LqBU">max-min item allocation</a>.</li></ul>

Multiple subset sum open-in-new

Multiple subset sum