Multiple subset sum

Last updated February 17, 2023

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

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: ( {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:^[5]

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

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]

Related Research Articles

<span class="mw-page-title-main">Knapsack problem</span> Problem in combinatorial optimization

The knapsack problem is the following problem in combinatorial optimization:

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset $of integers and a target-sum, and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:$

In computational complexity theory, the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed multiplicative factor of the optimal answer.

A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least $times the correct value, and at most times the correct value.$

Uniform machine scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m different machines. The goal is to minimize the makespan - the total time required to execute the schedule. The time that machine i needs in order to process job j is denoted by p_i,j. In the general case, the times p_i,j are unrelated, and any matrix of positive processing times is possible. In the specific variant called uniform machine scheduling, some machines are uniformly faster than others. This means that, for each machine i, there is a speed factor s_i, and the run-time of job j on machine i is p_i,j = p_j / s_i.

In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task might vary from one agent to the other.

Exact division, also called consensus division, is a partition of a continuous resource ("cake") into some k pieces, such that each of n people with different tastes agree on the value of each of the pieces. For example, consider a cake which is half chocolate and half vanilla. Alice values only the chocolate and George values only the vanilla. The cake is divided into three pieces: one piece contains 20% of the chocolate and 20% of the vanilla, the second contains 50% of the chocolate and 50% of the vanilla, and the third contains the rest of the cake. This is an exact division (with k=3 and n=2), as both Alice and George value the three pieces as 20%, 50% and 30% respectively. Several common variants and special cases are known by different terms:

In computational complexity theory, a branch of computer science, the Max/min CSP/Ones classification theorems state necessary and sufficient conditions that determine the complexity classes of problems about satisfying a subset S of boolean relations. They are similar to Schaefer's dichotomy theorem, which classifies the complexity of satisfying finite sets of relations; however, the Max/min CSP/Ones classification theorems give information about the complexity of approximating an optimal solution to a problem defined by S.

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.

A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain in prior-free mechanisms and prior-independent mechanisms.

The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of items to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al. The 0-1 quadratic knapsack problem is a variation of knapsack problems, combining the features of unbounded knapsack problem, 0-1 knapsack problem and quadratic knapsack problem.

Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items into n parts and taking the part with the minimum value.

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the Identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers, whose sum is k*T.

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.

Identical-machines scheduling is an optimization problem in computer science and operations research. We are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m identical machines, such that a certain objective function is optimized, for example, the makespan is minimized.

Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J₁, J₂, ..., J_n on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by p_i,j. The term unrelated emphasizes that there is no relation between values of p_i,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which p_i,j = p_i / s_j, and identical-machines scheduling - in which p_i,j = p_i.

Matroid-constrained number partitioning is a variant of the multiway number partitioning problem, in which the subsets in the partition should be independent sets of a matroid. The input to this problem is a set S of items, a positive integer m, and some m matroids over the same set S. The goal is to partition S into m subsets, such that each subset i is an independent set in matroid i. Subject to this constraint, some objective function should be minimized, for example, minimizing the largest sum item sizes in a subset. In a more general variant, each of the m matroids has a weight function, which assigns a weight to each element of the ground-set. Various objective functions have been considered. For each of the three operators max,min,sum, one can use this operator on the weights of items in each subset, and on the subsets themselves. All in all, there are 9 possible objective functions, each of which can be maximized or minimized.

The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.

References

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:1-1] 1 2 3 Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). "The Multiple Subset Sum Problem". SIAM Journal on Optimization. 11 (2): 308–319. doi:10.1137/S1052623498348481. ISSN 1052-6234.

[2] Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-29). "A PTAS for the Multiple Subset Sum Problem with different knapsack capacities". Information Processing Letters. 73 (3–4): 111–118. doi:10.1016/S0020-0190(00)00010-7. ISSN 0020-0190.

[3] Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2003-03-01). "A 3/4-Approximation Algorithm for Multiple Subset Sum". Journal of Heuristics. 9 (2): 99–111. doi:10.1023/A:1022584312032. ISSN 1572-9397. S2CID 1120180.

[4] Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2015). Hoefer, Martin (ed.). "Brief Announcement: On the Fair Subset Sum Problem". Algorithmic Game Theory. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 9347: 309–311. doi:10.1007/978-3-662-48433-3_28. ISBN 978-3-662-48433-3.

[:2-5] 1 2 Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2017-03-16). "Price of Fairness for allocating a bounded resource". European Journal of Operational Research. 257 (3): 933–943. arXiv: 1508.05253 . doi:10.1016/j.ejor.2016.08.013. ISSN 0377-2217. S2CID 14229329.

[6] Chandra Chekuri and Sanjeev Khanna (2005). "A PTAS for the multiple knapsack problem". SIAM Journal on Computing. 35 (3): 713–728. CiteSeerX 10.1.1.226.3387 . doi:10.1137/s0097539700382820.

[1]

[2]

[3]

[4]

[5]

[6]