Faster Pseudopolynomial Time Algorithms for Subset Sum

DOI10.1145/3329863MaRDI QIDQ4972686zbMATH OpenOpenAlexFDO

Authors Konstantinos Koiliaris, Chao Xu

Publication date 25 November 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

convolutionsubset sum

Mathematics Subject Classification ID

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

Abstract: Given a multiset $S$ of $n$ positive integers and a target integer $t$, the subset sum problem is to decide if there is a subset of $S$ that sums up to $t$. We present a new divide-and-conquer algorithm that computes all the realizable subset sums up to an integer $u$ in $widetildeO!left(minsqrtnu,u^{4/3},sigmaight)$, where $sigma$ is the sum of all elements in $S$ and $widetildeO$ hides polylogarithmic factors. This result improves upon the standard dynamic programming algorithm that runs in $O(nu)$ time. To the best of our knowledge, the new algorithm is the fastest general algorithm for this problem. We also present a modified algorithm for cyclic groups, which computes all the realizable subset sums within the group in $widetildeO!left(minsqrtnm,m^{5/4}ight)$ time, where $m$ is the order of the group.

Recommendations

• A faster pseudopolynomial time algorithm for subset sum
• A near-linear pseudopolynomial time algorithm for subset sum
• Faster algorithms for \(k\)-\textsc{Subset Sum} and variations
• Faster algorithms for \(k\)-subset sum and variations
• Faster space-efficient algorithms for subset sum and k-sum
• A Fast Approximation Algorithm For The Subset-Sum Problem
• A Fast Approximation Algorithm for the Subset-sum Problem
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• A faster FPTAS for the subset-sums ratio problem
• scientific article; zbMATH DE number 1223719

Cites work

• A faster pseudopolynomial time algorithm for subset sum
• A near-linear pseudopolynomial time algorithm for subset sum
• A new lower bound for the open-shop problem
• A Structural Approach to Subset-Sum Problems
• A subquadratic approximation scheme for partition
• An addition theorem modulo p
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• Balanced cut approximation in random geometric graphs
• Computing Partitions with Applications to the Knapsack Problem
• Covering Sets for Limited-Magnitude Errors
• Discrete-variable extremum problems
• Dynamic programming on the word RAM
• Dynamic programming revisited: Improving knapsack algorithms
• Efficient Computation of Power Indices for Weighted Majority Games
• Estimation de la fonction de Tchebychef θ sur le k-ième nombre premier et grandes valeurs de la fonction ω(n) nombre de diviseurs premiers de n
• Fast Approximation Algorithms for Knapsack Problems
• Fast modular subset sum using linear sketching
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Finding witnesses by peeling
• scientific article; zbMATH DE number 3856407 (Why is no real title available?)
• scientific article; zbMATH DE number 3928865 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 176777 (Why is no real title available?)
• scientific article; zbMATH DE number 1286510 (Why is no real title available?)
• scientific article; zbMATH DE number 1310280 (Why is no real title available?)
• scientific article; zbMATH DE number 1315279 (Why is no real title available?)
• scientific article; zbMATH DE number 1034105 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 3102822 (Why is no real title available?)
• Introduction to algorithms
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Minimum Range Balanced Cuts via Dynamic Subset Sums
• On a conjecture of Erdös and Heilbronn
• On complete subsets of the cyclic group
• On covering by translates of a set
• On the complexity of k-SAT
• On Δ(x, n) = ϕ(x, n) - xϕ(n)/n
• Parallel machine scheduling with job assignment restrictions
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Reducibility among combinatorial problems
• Saving space by algebraization
• SETH-based lower bounds for subset sum and bicriteria path
• Structural approach to subset sum problems
• Subset sums
• Sums of sets of group elements
• Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning

Cited in

(39)

• More on change-making and related problems
• Faster algorithms for \(k\)-subset sum and variations
• Approximation algorithms for some extensions of the maximum profit routing problem
• Scheduling lower bounds via AND subset sum
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• The Modular Subset-Sum Problem and the size of deletion correcting codes
• Approximating subset sum ratio via subset sum computations
• The complexity of unary subset sum
• Irredundant Set Faster Than O(2 n )
• A faster pseudopolynomial time algorithm for subset sum
• A near-linear pseudopolynomial time algorithm for subset sum
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Fast Monotone Summation over Disjoint Sets
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Equal-subset-sum faster than the meet-in-the-middle
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• SETH-based lower bounds for subset sum and bicriteria path
• Fast modular subset sum using linear sketching
• scientific article; zbMATH DE number 5057523 (Why is no real title available?)
• scientific article; zbMATH DE number 7651168 (Why is no real title available?)
• Generalization of the subset sum problem and cubic forms
• Algebraic algorithms for variants of subset sum
• One-dimensional stock cutting resilient against singular random defects
• Faster algorithms for \(k\)-\textsc{Subset Sum} and variations
• Quick minimization of tardy processing time on a single machine
• 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
• Scheduling lower bounds via and subset sum
• Minimizing tardy processing time on a single machine in near-linear time
• On the parameterized complexity of diverse SAT
• On two simple[st] learning tasks
• Minimizing tardy processing time on a single machine in near-linear time
• Almost optimum \(\ell \)-covering of \(\mathbb{Z}_n\)
• Knapsack and subset sum with small items
• Parameterized algorithms on integer sets with small doubling: integer programming, subset sum and k-SUM
• On the parameterized complexity of diverse SAT
• Does subset sum admit short proofs?
• Weakly approximating knapsack in subquadratic time

This page was built for publication: Faster Pseudopolynomial Time Algorithms for Subset Sum

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