Multiple subset sum explained

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.
• 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 a₁,...,a_n of EPART with target sum T, construct an instance 2T+a₁, ..., 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 < 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.^[2]
  • A 3/4-approximation algorithm which runs in time O(m²n). ^[3]
• 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.

Fair subset sum problem

The fair subset sum problem^[4] (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:^[5]

• For shared items: define a 2-dimensional array

Q such that Q(w _{1,w} _{2)=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 ⋅ 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)=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 ⋅ 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.

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.^[6]

Notes and References

1. Caprara. Alberto. Kellerer. Hans. Pferschy. Ulrich. 2000-02-01. The Multiple Subset Sum Problem. SIAM Journal on Optimization. 11. 2. 308–319. 10.1137/S1052623498348481. 1052-6234.
2. 2000-02-29. A PTAS for the Multiple Subset Sum Problem with different knapsack capacities. Information Processing Letters. en. 73. 3–4. 111–118. 10.1016/S0020-0190(00)00010-7. 0020-0190. Caprara . Alberto . Kellerer . Hans . Pferschy . Ulrich .
3. Caprara. Alberto. Kellerer. Hans. Pferschy. Ulrich. 2003-03-01. A 3/4-Approximation Algorithm for Multiple Subset Sum. Journal of Heuristics. en. 9. 2. 99–111. 10.1023/A:1022584312032. 1120180 . 1572-9397.
4. Nicosia. Gaia. Pacifici. Andrea. Pferschy. Ulrich. 2015. Hoefer. Martin. Brief Announcement: On the Fair Subset Sum Problem. Algorithmic Game Theory. Lecture Notes in Computer Science. 9347 . en. Berlin, Heidelberg. Springer. 309–311. 10.1007/978-3-662-48433-3_28. 978-3-662-48433-3.
5. 2017-03-16. Price of Fairness for allocating a bounded resource. European Journal of Operational Research. en. 257. 3. 933–943. 10.1016/j.ejor.2016.08.013. 0377-2217. 1508.05253. Nicosia . Gaia . Pacifici . Andrea . Pferschy . Ulrich . 14229329 .
6. Chandra Chekuri and Sanjeev Khanna. 2005. A PTAS for the multiple knapsack problem. SIAM Journal on Computing. 35. 3. 713–728. 10.1.1.226.3387. 10.1137/s0097539700382820.