Multiple subset sum

<h2 id="max-sum-and-max-min-mssp">Max-sum and max-min MSSP</h2>
When m is variable (a part of the input), both problems are <a href="/facts/Strongly_NP-hard/rqFp8pxx">strongly NP-hard</a>, by reduction from <a href="/facts/3-partition_problem/X4uW5f57">3-partition</a>. This means that they have no <a href="/facts/Fully_polynomial-time_approximation_scheme/52Chjx9y">fully polynomial-time approximation scheme</a> (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 <a href="/facts/Partition_problem/LcSBAcmu">partition problem</a> (EPART):

<ul><li>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.</li>
<li>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.</li>
<li>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)}
 
.</li>
<li>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.</li>
<li>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.</li></ul>
The following approximation algorithms are known:<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<ul><li>For max-sum MSSP, with variable m:
<ul><li>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.</li>
<li>A more general PTAS for the case in which the subset capacities are different.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>A 3/4-approximation algorithm which runs in time O(m2n). <a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li></ul></li>
<li>For max-min MSSP:
<ul><li>With variable m: a 2/3-approximation, in time O(n log n). No better approximation is possible unless P=NP (by reduction from <a href="/facts/3-partition_problem/X4uW5f57">3-partition</a>).</li>
<li>With fixed m: a PTAS, running in time 
 
 
 
 O
 (
 
 n
 
 2
 m
 
 /
 
 ϵ
 
 
 )
 
 
 {\displaystyle O(n^{2m/\epsilon })}
 
.</li>
<li>With a fixed number of distinct input values: a PTAS using <a href="/facts/Lenstra%2527s_algorithm/MDaaadoA">Lenstra's algorithm</a>.</li></ul></li></ul>
<h2 id="fair-subset-sum-problem">Fair subset sum problem</h2>
The fair subset sum problem<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> (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 <a href="/facts/Egalitarian_rule/pvL7sd7m">egalitarian rule</a> or the <a href="/facts/Proportional-fair_rule/XrlfaYP4">proportional-fair rule</a>. Two variants of the problem are:

<ul><li>Shared items: each item can be allocated to every agent. This setting is similar to <a href="/facts/Fair_item_allocation/Hvx2XrG9">fair item allocation</a> 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} ).</li>
<li>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.</li></ul>
Both variants are NP-hard. However, there are pseudopolynomial time algorithms for enumerating all Pareto-optimal solutions when there are two agents:<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<ul><li>For shared items: define a 2-dimensional array 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 such that 
 
 
 
 Q
 (
 
 w
 
 1
 
 
 ,
 
 w
 
 2
 
 
 )
 =
 
 true
 
 
 
 {\displaystyle Q(w_{1},w_{2})={\text{true}}}
 
 iff there exists a solution giving a total weight of wi to agent i. It is possible to enumerate all possible utility profiles in time 
 
 
 
 O
 (
 n
 ⋅
 
 c
 
 2
 
 
 )
 
 
 {\displaystyle O(n\cdot c^{2})}
 
 where n is the number of items and c is the maximum size of an item.</li>
<li>For separate items: for each agent j, define a dynamic array 
 
 
 
 
 Q
 
 j
 
 
 
 
 {\displaystyle Q_{j}}
 
, such that 
 
 
 
 
 Q
 
 j
 
 
 (
 w
 )
 =
 
 true
 
 
 
 {\displaystyle Q_{j}(w)={\text{true}}}
 
 iff there exists a solution giving a total weight of w to agent j. Each array 
 
 
 
 
 Q
 
 j
 
 
 
 
 {\displaystyle 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
 )
 
 
 {\displaystyle O(n\cdot c)}
 
.</li></ul>
Nicosia, Pacifici and Pferschy study the <a href="/facts/Price_of_fairness/vbA9vA51">price of fairness</a>, that is, the ratio between the maximum sum of utilities, and the maximum sum of utilities in a fair solution:

<ul><li>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.</li>
<li>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.</li>
<li>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.</li></ul>
In both cases, if the item value is bounded by some constant a, then the POF is bounded by a function of a.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="multiple-knapsack-problem">Multiple knapsack problem</h2>
The <a href="/facts/Multiple_knapsack_problem/HMIdVJH5">multiple knapsack problem</a> (MKP) is a generalization of both the max-sum MSSP and the <a href="/facts/Knapsack_problem/HMIdVJH5">knapsack problem</a>. 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. 

<ul><li>Max-sum MSSP is a special case of MKP in which the value of each item equals its weight.</li>
<li>The knapsack problem is a special case of MKP in which m=1.</li>
<li>The subset-sum problem is a special case of MKP in which both the value of each item equals its weight, and m=1.</li></ul>
The MKP has a <a href="/facts/Polynomial-time_approximation_scheme/52Chjx9y">Polynomial-time approximation scheme</a>.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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. <a href="https://doi.org/10.1137/S1052623498348481" target="_blank">https://doi.org/10.1137/S1052623498348481</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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. <a href="https://doi.org/10.1137/S1052623498348481" target="_blank">https://doi.org/10.1137/S1052623498348481</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="https://doi.org/10.1137/S1052623498348481" target="_blank">https://doi.org/10.1137/S1052623498348481</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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. <a href="https://www.sciencedirect.com/science/article/abs/pii/S0020019000000107" target="_blank">https://www.sciencedirect.com/science/article/abs/pii/S0020019000000107</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">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. <a href="https://doi.org/10.1023/A:1022584312032" target="_blank">https://doi.org/10.1023/A:1022584312032</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2015). "Brief Announcement: On the Fair Subset Sum Problem". In Hoefer, Martin (ed.). Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 9347. Berlin, Heidelberg: Springer. pp. 309–311. doi:10.1007/978-3-662-48433-3_28. ISBN 978-3-662-48433-3. <a href="978-3-662-48433-3" target="_blank">978-3-662-48433-3</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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. <a href="https://www.sciencedirect.com/science/article/abs/pii/S0377221716306282" target="_blank">https://www.sciencedirect.com/science/article/abs/pii/S0377221716306282</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">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. <a href="https://www.sciencedirect.com/science/article/abs/pii/S0377221716306282" target="_blank">https://www.sciencedirect.com/science/article/abs/pii/S0377221716306282</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">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. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Multiple subset sum open-in-new

Multiple subset sum