Space-Efficient Approximations for Subset Sum

Abstract

SubsetSum is a well-known NP-complete problem: given t∈ Z+ and a set S of m positive integers, output YES if and only if there is a subset S′⊆ S such that the sum of all numbers in S′ equals t. The problem and its search and optimization versions are known to be solvable in pseudopolynomial time in general. We develop a one-pass deterministic streaming algorithm that uses space O (log t/ε) and decides if some subset of the input stream adds up to a value in the range {(1±ϵ) t}. Using this algorithm, we design space-efficient fully polynomial-time approximation schemes (FPTAS) solving the search and optimization versions of SubsetSum. Our algorithms run in O (1/ϵ m 2) time and O (1/ϵ) space on unit-cost RAMs, where 1+ ϵ is the approximation factor. This implies constant space quadratic time FPTAS on unit-cost RAMs when ϵ is a constant. Previous FPTAS used space linear in m. In addition, we show that on certain inputs, when a solution is located within a short prefix of the input sequence, our algorithms may run in sublinear time. We apply our techniques to the problem of finding balanced separators, and we extend our results to some other variants of the more general knapsack problem. When the input numbers are encoded in unary, the decision version has been known to be in log space. We give streaming space lower and upper bounds for unary SubsetSum (USS). If the input length is N when the numbers are encoded in unary, we show that randomized s-pass streaming algorithms for exact SubsetSum need space Ω (√N/s) and give a simple deterministic two-pass streaming algorithm using O(√N log N) space. Finally, we formulate an encoding under which USS is monotone and show that the exact and approximate versions in this formulation have monotone O(log2t) depth Boolean circuits. We also show that any circuit using ε-approximator gates for SubsetSum under this encoding needs Ω(n/logn) gates to compute the disjointness function.