Faster Pseudopolynomial Time Algorithms for Subset Sum
From MaRDI portal
Publication:4972686
DOI10.1145/3329863zbMath1454.90076arXiv1507.02318OpenAlexW2952672079MaRDI QIDQ4972686
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
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (17)
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 ⋮ 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 ⋮ Unnamed Item ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Unnamed Item ⋮ More on change-making and related problems ⋮ Faster Pseudopolynomial Time Algorithms for Subset Sum ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ Faster algorithms for \(k\)-subset sum and variations ⋮ Approximation algorithms for some extensions of the maximum profit routing problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Structural approach to subset sum problems
- On complete subsets of the cyclic group
- Balanced cut approximation in random geometric graphs
- Subset sums
- Dynamic programming on the word RAM
- A new lower bound for the open-shop problem
- Dynamic programming revisited: Improving knapsack algorithms
- Saving space by algebraization
- Covering Sets for Limited-Magnitude Errors
- On covering by translates of a set
- Finding witnesses by peeling
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- A Structural Approach to Subset-Sum Problems
- Fast Approximation Algorithms for Knapsack Problems
- 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
- An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
- Sums of sets of group elements
- Computing Partitions with Applications to the Knapsack Problem
- Minimum Range Balanced Cuts via Dynamic Subset Sums
- A Faster Pseudopolynomial Time Algorithm for Subset Sum
- A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
- On Δ(x, n) = ϕ(x, n) - xϕ(n)/n
- Efficient Computation of Power Indices for Weighted Majority Games
- Linear Time Algorithms for Knapsack Problems with Bounded Weights
- Faster Pseudopolynomial Time Algorithms for Subset Sum
- Reducibility among Combinatorial Problems
- SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
- Fast Modular Subset Sum using Linear Sketching
- A Subquadratic Approximation Scheme for Partition
- Discrete-Variable Extremum Problems
- Parallel machine scheduling with job assignment restrictions
- An addition theorem modulo p
- On a conjecture of Erdös and Heilbronn
- Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning
- On the complexity of \(k\)-SAT
This page was built for publication: Faster Pseudopolynomial Time Algorithms for Subset Sum
