Faster Pseudopolynomial Time Algorithms for Subset Sum
type: Item
instance of: scholarly article
title: Faster Pseudopolynomial Time Algorithms for Subset Sum
zbMATH Open document ID: 1454.90076
DOI: 10.1145/3329863
author: Konstantinos Koiliaris
author: Chao Xu
published in: ACM Transactions on Algorithms
publication date: 2019-11-25T00:00:00Z
full work available at URL: https://arxiv.org/abs/1507.02318
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 7136432
zbMATH Keywords: subset sum
zbMATH Keywords: convolution
MaRDI profile type: Publication
OpenAlex ID: W2952672079
arXiv ID: 1507.02318
cites work: SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
cites work: Subset sums
cites work: Finding witnesses by peeling
cites work: Fast Modular Subset Sum using Linear Sketching
cites work: Q3703780
cites work: On covering by translates of a set
cites work: A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
cites work: Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
cites work: Q4242959
cites work: Q4256495
cites work: Covering Sets for Limited-Magnitude Errors
cites work: Introduction to algorithms
cites work: Discrete-Variable Extremum Problems
cites work: Balanced cut approximation in random geometric graphs
cites work: Minimum Range Balanced Cuts via Dynamic Subset Sums
cites work: Q5841589
cites work: Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning
cites work: An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
cites work: Q4036607
cites work: Parallel machine scheduling with job assignment restrictions
cites work: A new lower bound for the open-shop problem
cites work: On complete subsets of the cyclic group
cites work: Q3856819
cites work: Q4344458
cites work: Computing Partitions with Applications to the Knapsack Problem
cites work: On the complexity of \(k\)-SAT
cites work: Reducibility among Combinatorial Problems
cites work: Q4821303
cites work: Q4254354
cites work: A Faster Pseudopolynomial Time Algorithm for Subset Sum
cites work: Fast Approximation Algorithms for Knapsack Problems
cites work: Saving space by algebraization
cites work: A Subquadratic Approximation Scheme for Partition
cites work: An addition theorem modulo p
cites work: Sums of sets of group elements
cites work: Dynamic programming revisited: Improving knapsack algorithms
cites work: Linear Time Algorithms for Knapsack Problems with Bounded Weights
cites work: Dynamic programming on the word RAM
cites work: 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
cites work: Q3325040
cites work: On Δ(x, n) = ϕ(x, n) - xϕ(n)/n
cites work: Structural approach to subset sum problems
cites work: On a conjecture of Erdös and Heilbronn
cites work: Efficient Computation of Power Indices for Weighted Majority Games
cites work: A Structural Approach to Subset-Sum Problems
Recommended article: A Faster Pseudopolynomial Time Algorithm for Subset Sum
Recommended article: A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
Recommended article: Faster algorithms for \(k\)-\textsc{Subset Sum} and variations
Recommended article: Faster algorithms for \(k\)-subset sum and variations
Recommended article: Faster space-efficient algorithms for subset sum and k-sum
Recommended article: A Fast Approximation Algorithm For The Subset-Sum Problem
Recommended article: A Fast Approximation Algorithm for the Subset-sum Problem
Recommended article: Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
Recommended article: A faster FPTAS for the subset-sums ratio problem
Recommended article: Q4219034
description: scientific article; zbMATH DE number 7136432