A near-linear pseudopolynomial time algorithm for subset sum

DOI10.1137/1.9781611974782.69MaRDI QIDQ4575810zbMATH OpenOpenAlexFDO

Authors Karl Bringmann

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.04712

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)

Abstract: Given a set $Z$ of $n$ positive integers and a target value $t$, the Subset Sum problem asks whether any subset of $Z$ sums to $t$. A textbook pseudopolynomial time algorithm by Bellman from 1957 solves Subset Sum in time $O(nt)$. This has been improved to $O(nmaxZ)$ by Pisinger [J. Algorithms'99] and recently to $ildeO(sqrtnt)$ by Koiliaris and Xu [SODA'17]. Here we present a simple randomized algorithm running in time $ildeO(n+t)$. This improves upon a classic algorithm and is likely to be near-optimal, since it matches conditional lower bounds from Set Cover and k-Clique. We then use our new algorithm and additional tricks to improve the best known polynomial space solution from time $ildeO(n^{3}t)$ and space $ildeO(n^2)$ to time $ildeO(nt)$ and space $ildeO(nlogt)$, assuming the Extended Riemann Hypothesis. Unconditionally, we obtain time $ildeO(n{t}^{1+varepsilon})$ and space $ildeO(n{t}^{v}arepsilon)$ for any constant $varepsilon>0$.

Recommendations

• A faster pseudopolynomial time algorithm for subset sum
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Faster space-efficient algorithms for subset sum and k-sum
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Faster algorithms for \(k\)-subset sum and variations

Cited in

(57)

• Change-making problems revisited: a parameterized point of view
• An improved balanced algorithm for the subset-sum problem
• More on change-making and related problems
• Faster algorithms for \(k\)-subset sum and variations
• Scheduling lower bounds via AND subset sum
• Faster minimization of tardy processing time on a single machine
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Approximating subset sum ratio via subset sum computations
• Approximating multidimensional subset sum and Minkowski decomposition of polygons
• Constant time approximation scheme for largest well predicted subset
• Saving space by algebraization
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• The complexity of unary subset sum
• Subset sum in the absence of concentration
• scientific article; zbMATH DE number 4035132 (Why is no real title available?)
• A faster pseudopolynomial time algorithm for subset sum
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Faster space-efficient algorithms for subset sum and k-sum
• Equal-subset-sum faster than the meet-in-the-middle
• An Average-Case Sublinear Exact Li and Stephens Forward Algorithm
• On integer programming and convolution
• Fine-Grained Complexity Theory (Tutorial)
• Capacitated dynamic programming: faster knapsack and graph algorithms
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• On binary solutions to systems of equations
• SETH-based lower bounds for subset sum and bicriteria path
• Fast modular subset sum using linear sketching
• Space-time tradeoffs for subset sum: an improved worst case algorithm
• A Logarithmic Bound for Solving Subset Sum with P Systems
• scientific article; zbMATH DE number 5057523 (Why is no real title available?)
• scientific article; zbMATH DE number 7651168 (Why is no real title available?)
• SETH-based Lower Bounds for Subset Sum and Bicriteria Path
• From approximate to exact integer programming
• Algebraic algorithms for variants of subset sum
• Faster algorithms for \(k\)-\textsc{Subset Sum} and variations
• Efficient reductions and algorithms for subset product
• Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
• Approximating subset sum ratio via partition computations
• A simple near-linear pseudopolynomial time randomized algorithm for subset sum
• \(k\)-SUM in the sparse regime: complexity and applications
• On Wagner's k-tree algorithm over integers
• Faster minimization of tardy processing time on a single machine
• Scheduling lower bounds via and subset sum
• Minimizing tardy processing time on a single machine in near-linear time
• Space-efficient algorithm for integer programming with few constraints
• Minimizing tardy processing time on a single machine in near-linear time
• Classical and quantum algorithms for variants of subset-sum via dynamic programming
• Almost optimum \(\ell \)-covering of \(\mathbb{Z}_n\)
• From approximate to exact integer programming
• Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
• Fast n-fold Boolean convolution via additive combinatorics
• Knapsack and subset sum with small items
• Even faster knapsack via rectangular monotone min-plus convolution and balancing
• Parameterized algorithms on integer sets with small doubling: integer programming, subset sum and k-SUM
• Does subset sum admit short proofs?
• Convolution and knapsack in higher dimensions
• Weakly approximating knapsack in subquadratic time

This page was built for publication: A near-linear pseudopolynomial time algorithm for subset sum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575810)