- 标题：Space-Efficient Approximations for Subset Sum
- 本地全文：下载
- 作者：Anna Gal ; Jing-Tang Jang ; Nutan Limaye 等
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2014
- 卷号：2014
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
SUBSET SUM 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 optimization versions of SUBSET SUM. 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 SUBSET SUM. If the input length is N when the numbers are encoded in unary, we show that randomized s -pass streaming algorithms for exact SUBSET SUM need space ( s N ) , and give a simple deterministic two pass streaming algorithm using O ( N log N ) space.

Finally, we formulate an encoding under which unary SUBSET SUM is monotone, and show that the exact and approximate versions in this formulation have monotone O ( log 2 t ) depth Boolean circuits. We also show that any circuit using -approximator gates for Subset Sum under this encoding needs ( n log n ) gates to compute the Disjointness function.

- 关键词：Approximation ; space complexity ; Streaming Algorithms ; Subset Sum