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 pseudo-polynomial time in general. We develop a 1-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 opti-mization versions of SubsetSum. Our algorithms run in O ( 1 m2) 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. 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 Ω(