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 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 . * 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.

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 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 . 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. 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 a 1 ,...,a n of EPART with target sum T, construct an instance 2T+a 1 , ..., 2T+a n 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) . Therefore, for any \epsilon , any algorithm with approximation ratio (1-\epsilon) must find the optimal solution if it exists. If we had an FPTAS, then we would have an algorithm with e.g. \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 \epsilon is fixed. The run-time is at least exponential in 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(m 2 n). 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^{2m/\epsilon}) . With a fixed number of distinct input values: a PTAS using Lenstra's algorithm. For shared items: define a 2-dimensional array Q such that Q(w_1,w_2)=\text{true} iff there exists a solution giving a total weight of w i to agent i. It is possible to enumerate all possible utility profiles in time O(n\cdot c^2) where n is the number of items and c is the maximum size of an item. For separate items: for each agent j, define a dynamic array Q_j , such that Q_j(w)=\text{true} iff there exists a solution giving a total weight of w to agent j. Each array Q_j can be constructed separately using the separate items of agent j. Then, one can traverse the two arrays in opposite directions and enumerate all allocations in the Pareto frontier. The run-time is O(n\cdot c) . 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: For shared items: the price-of-fairness of max-min fairness is unbounded. For example, suppose there are four items with values 1, e, e, e, for some small e>0. The maximum sum is 1, attained by giving one agent the item with value 1 and the other agent nothing. But the max-min allocation gives each agent value at least e, so the sum must be at most 3e. Therefore the POF is 1/(3e), which is unbounded. Alice has two items with values 1 and e, for some small e>0. George has two items with value e. The capacity is 1. The maximum sum is 1, attained by giving Alice the item with value 1 and George nothing. But the max-min allocation gives both agents value e. Therefore the POF is 1/(2e), which is unbounded. For separate items: the price-of-fairness of max-min fairness is unbounded. For example, suppose Alice has two items with values 1 and e, for some small e>0. George has two items with value e. The capacity is 1. The maximum sum is 1 - when Alice gets the item with value 1 and George gets nothing. But the max-min allocation gives both agents value e. Therefore the POF is 1/(2e), which is unbounded. In both cases, if the item value is bounded by some constant a, then the POF is bounded by a function of a. The knapsack problem is a special case of MKP in which m=1. The subset-sum problem is a special case of MKP in which both the value of each item equals its weight, and m=1. The MKP has a Polynomial-time approximation scheme.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1321258610 under CC BY-SA 4.0; modifications have been made.