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 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:
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. 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. 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.
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):
Given an instance a1,...,an of EPART with target sum T, construct an instance 2T+a1, ..., 2T+an of MSSP with target sum (n+1)T for both subsets. A solution to EPART consists of two parts, each of which has n/2 elements with a sum of T. It corresponds to an optimal solution of both MSSP variants: two subsets with a sum of (n+1)T, which is the largest possible. Similarly, each optimal solution of MSSP corresponds to a solution to EPART. Any non-optimal solution to MSSP leaves at least one item unallocated, so its sum is at most 2nT and its minimum is at most nT. In both variants, the approximation ratio is at most 1 − 1 / ( n + 1 ) {\displaystyle 1-1/(n+1)} . Therefore, for any ϵ < 1 / ( n + 1 ) {\displaystyle \epsilon <1/(n+1)} , any algorithm with approximation ratio ( 1 − ϵ ) {\displaystyle (1-\epsilon )} must find the optimal solution if it exists. If we had an FPTAS, then we would have an algorithm with e.g. ϵ = 1 / ( n + 2 ) {\displaystyle \epsilon =1/(n+2)} , with run-time polynomial in n. This algorithm could be used to solve EPART in time polynomial in n. But this is not possible unless P=NP. The following approximation algorithms are known:
For max-sum MSSP, with variable m: A PTAS, which runs in time O(m+n) when ϵ {\displaystyle \epsilon } is fixed. The run-time is at least exponential in 1 / ϵ 2 {\displaystyle 1/\epsilon ^{2}} , and the authors consider it impractical. A more general PTAS for the case in which the subset capacities are different. A 3/4-approximation algorithm which runs in time O(m2n). For max-min MSSP: With variable m: a 2/3-approximation, in time O(n log n). No better approximation is possible unless P=NP (by reduction from 3-partition). With fixed m: a PTAS, running in time O ( n 2 m / ϵ ) {\displaystyle O(n^{2m/\epsilon })} . With a fixed number of distinct input values: a PTAS using Lenstra's algorithm.
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:
Shared items: each item can be allocated to every agent. This setting is similar to fair item allocation with identical valuations (the value of each item is the same for all agents and equals the item weight), however, there is an additional capacity constraint on the total weight of items. As an example, suppose the item weights are 3,5,7,9 and the capacity is 15. Then, some possible allocations are: ( {3,5,7}, {} ); ( {3,5}, {7} ); ( {5}, {3,7} ); ( {5}, {9} ). Of these allocations, the one satisfying the max-min criterion is ( {3,5}, {7} ). Separate items: for each agent, there is a separate set of items that can be allocated only to him/her. This setting is relevant when there is a budget that should be allocated to different projects, where each project belongs to a unique agent. Both variants are NP-hard. However, there are pseudopolynomial time algorithms for enumerating all Pareto-optimal solutions when there are two agents:
… excerpt ends here. Continue reading the full article.
