subset sum problem

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T , and the question is to decide whether any subset of the integers sum to precisely T . The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example: * The variant in which all inputs are positive. * The variant in which inputs may be positive or negative, and T=0 . For example, given the set \{-7, -3, -2, 9000, 5, 8\} , the answer is yes because the subset \{-3, -2, 5\} sums to zero. * The variant in which all inputs are positive, and the target sum is exactly half the sum of all inputs, i.e., T = \frac{1}{2}(a_1+\dots+a_n) . This special case of SSP is known as the partition problem. SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice. SSP is a special case of the knapsack problem and of the multiple subset sum problem.

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T , and the question is to decide whether any subset of the integers sum to precisely T . The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example: The variant in which all inputs are positive. The variant in which inputs may be positive or negative, and T=0 . For example, given the set \{-7, -3, -2, 9000, 5, 8\} , the answer is yes because the subset \{-3, -2, 5\} sums to zero. The variant in which all inputs are positive, and the target sum is exactly half the sum of all inputs, i.e., T = \frac{1}{2}(a_1+\dots+a_n) . This special case of SSP is known as the partition problem. SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice. SSP is a special case of the knapsack problem and of the multiple subset sum problem. We are given an instance of 3DM, where the vertex sets are W, X, Y. Each set has n vertices. There are m edges, where each edge contains exactly one vertex from each of W, X, Y. Denote L := ceiling(log 2 (m+1)), so that L is larger than the number of bits required to represent the number of edges. We construct an instance of SSP with m positive integers. The integers are described by their binary representation. Each input integer can be represented by 3nL bits, divided into 3n zones of L bits. Each zone corresponds to a vertex. For each edge (w,x,y) in the 3DM instance, there is an integer in the SSP instance, in which exactly three bits are "1": the least-significant bits in the zones of the vertices w, x, and y. For example, if n=10 and L=3, and W=(0,...,9), X=(10,...,19), Y=(20,...,29), then the edge (0, 10, 20) is represented by the number (2 0 +2 30 +2 60 ). The target sum T in the SSP instance is set to an integer with "1" in the least-significant bit of every zone, that is, (2 0 +2 1 +...+2 3n-1 ). If the 3DM instance has a perfect matching, then summing the corresponding integers in the SSP instance yields exactly T. Conversely, if the SSP instance has a subset with sum exactly T, then, since the zones are sufficiently large so that there are no "carries" from one zone to the next, the sum must correspond to a perfect matching in the 3DM instance. The following variants are also known to be NP-hard: The input integers can be both positive and negative, and the target-sum T = 0. This can be proved by reduction from the variant with positive integers. Denote that variant by SubsetSumPositive and the current variant by SubsetSumZero. Given an instance (S, T) of SubsetSumPositive, construct an instance of SubsetSumZero by adding a single element with value −T. Given a solution to the SubsetSumPositive instance, adding the −T yields a solution to the SubsetSumZero instance. Conversely, given a solution to the SubsetSumZero instance, it must contain the −T (since all integers in S are positive), so to get a sum of zero, it must also contain a subset of S with a sum of +T, which is a solution of the SubsetSumPositive instance. The input integers are positive, and T = sum(S)/2. This can also be proved by reduction from the general variant; see partition problem. The analogous counting problem #SSP, which asks to enumerate the number of subsets summing to the target, is #P-complete. In 2014, Curtis and Sanches found a simple recursion highly scalable in SIMD machines having O(N(m-x_{\min})/p) time and O(N+m-x_{\min}) space, where is the number of processing elements, m=\min(s, \sum x_i - s) and x_{\min} is the lowest integer. This is the best theoretical parallel complexity known so far. A comparison of practical results and the solution of hard instances of the SSP is discussed by Curtis and Sanches. y = z add z to L return the largest element in L. Note that without the trimming step (the inner "for each" loop), the list L would contain the sums of all 2^n subsets of inputs. The trimming step does two things: It ensures that all sums remaining in L are below T, so they are feasible solutions to the subset-sum problem. It ensures that the list L is "sparse", that is, the difference between each two consecutive partial-sums is at least \epsilon T/n . These properties together guarantee that the list contains no more than n/\epsilon elements; therefore the run-time is polynomial in n/\epsilon . When the algorithm ends, if the optimal sum is in , then it is returned and we are done. Otherwise, it must have been removed in a previous trimming step. Each trimming step introduces an additive error of at most \epsilon T/n , so steps together introduce an error of at most \epsilon T . Therefore, the returned solution is at least \text{OPT}-\epsilon T which is at least (1-\epsilon)\text{OPT} . The above algorithm provides an exact solution to SSP in the case that the input numbers are small (and non-negative). If any sum of the numbers can be specified with at most bits, then solving the problem approximately with \epsilon = 2^{-P} is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in and 2^P (i.e., exponential in ). Kellerer, Mansini, Pferschy and Speranza and Kellerer, Pferschy and Pisinger present other FPTASes for subset sum. ==Further reading== A3.2: SP13, pg.223.

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