2020/11/07 by Ce Jin, Nikhil Vyas, Jin, Ce +3 · 1 citation
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2011.03819
openalex publication_date 2020/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the canonical Subset Sum problem: given a list of positive integers a1,…,an and a target integer t with t > ai for all i, determine if there is an S ⊆ [n] such that ∑i ∈ S ai = t. The well-known pseudopolynomial-time dynamic programming algorithm [Bellman, 1957] solves Subset Sum in O(nt) time, while requiring Ω(t) space. In this paper we present algorithms for Subset Sum with O(nt) running time and much lower space requirements than Bellman's algorithm, as well as that of prior work. We show that Subset Sum can be solved in O(nt) time and O(log(nt)) space with access to O(log n log log n+log t) random bits. This significantly improves upon the O(n t1+ε)-time, O(nlog t)-space algorithm of Bringmann (SODA 2017). We also give an O(n1+εt)-time, O(log(nt))-space randomized algorithm, improving upon previous (nt)O(1)-time O(log(nt))-space algorithms by Elberfeld, Jakoby, and Tantau (FOCS 2010), and Kane (2010). In addition, we also give a poly log(nt)-space, O(n2 t)-time deterministic algorithm. We also study time-space trade-offs for Subset Sum. For parameter 1≤ k≤ min\n,t\, we present a randomized algorithm running in O((n+t)⋅ k) time and O((t/k) polylog (nt)) space. As an application of our results, we give an O(min\n2/ε, n/ε2\)-time and polylog(nt)-space algorithm for "weak" ε-approximations of Subset Sum.