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.

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 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''₁,...,''a''_n of EPART with target sum ''T'', construct an instance 2''T''+''a''₁, ..., 2''T''+''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 2''nT'' and its minimum is at most ''nT''. In both variants, the approximation ratio is at most $1- 1/(n+1)$.
* Therefore, for any $\epsilon < 1/(n+1)$, 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²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^)$.
** 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: ( , ); ( , ); ( , ); ( , ). Of these allocations, the one satisfying the max-min criterion is ( , ).
* ''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:

* For shared items: define a 2-dimensional array $Q$ such that $Q(w_1,w_2)=\text$ 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$ 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 3''e''. Therefore the POF is 1/(3''e''), 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/(2''e''), 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/(2''e''), 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''.

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.

* Max-sum MSSP is a special case of MKP in which the value of each item equals its weight.
* 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.

References

{{reflist

Optimization algorithms and methods